perm filename KRD7.MSS[PEG,DBL]1 blob
sn#453061 filedate 1979-06-30 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00046 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 .S(Strategies, meta-rules for guidance)
C00010 00003 .SS(The main ideas,MAINIDEAS:)
C00018 00004 .SS(What is a strategy,WIAS:)
C00019 00005 .SSS(Ill structured problems, STRATISP:)
C00029 00006 .SSS(Strategies,STRATDEF:)
C00034 00007 .SSSS(Strategies as meta-level knowledge,STRATASMLK:)
C00041 00008 .SSSS(Strategies as a means of defining and choosing invocation criteria)
C00043 00009 .SSS(Levels of knowledge)
C00050 00010 .SSS(|Building blocks:# Conceptual primitives, language|, STRATBB:)
C00055 00011 .SKIP TO LINE 1SS(Meta-rules, STRATMR:)
C00063 00012 .SSS(Function)
C00067 00013 .SSSS(Details,STRATMRDETAILS:)
C00076 00014 .SSS(Implications of meta-rules as a strategy encoding)
C00084 00015 .SSS(Advanced issues,stratadviss:)
C00086 00016 .SSSS(Meta-rule organization:# Static)
C00092 00017 .SSSS(Encoding control structure information,STRATCSINFO:)
C00097 00018 .SSSS(Encoding design decision information)
C00100 00019 .SSS(Explanation and acquisition,STRATEXPLACQ:)
C00106 00020 .SSS(|Limitations of the current implementation, future work|,STRATFUTWORK:)
C00115 00021 .SKIP TO LINE 1SS(Broader implications,STRATBROADI:)
C00117 00022 .SSS(Reference by name vs. reference by description)
C00124 00023 .SSS(Benefits of content reference as an invocation mechanism,STRATGENERALI:)
C00126 00024 .SSSS(Reliability and expressiveness)
C00150 00025 .FULLPAGEFIG <<KS INVOCATION MECHANISM TABLE>>
C00153 00026 .FULLPAGEFIG APART <<EXPRESSIVENESS-RELIABILITY graph>>
C00155 00027 .SKIP TO LINE 1 SSSS(Generalized invocation criteria,STRATGIC:)
C00170 00028 .SSSS(Flexibility,STRATFLEX:)
C00181 00029 .FULLPAGEFIG << flexibility benchmarks>>
C00183 00030 .SKIP TO LINE 1SSS(Limitations)
C00193 00031 .SSSS(Expressiveness and generalized invocation criteria)
C00196 00032 .SSSS(Flexibility)
C00198 00033 .SSSS(Speed)
C00207 00034 .SSSS(Limitations:# Summary)
C00208 00035 .SSS(Future applications:# Choosing control regimes,STRATEXTIMEFLEX:)
C00218 00036 .SSS(Review)
C00222 00037 .SKIP TO LINE 1 SS(|A Taxonomy, of sorts|,STRATAX:)
C00224 00038 .SSS(Generality)
C00229 00039 .SSS(Degree of explicitness)
C00234 00040 .SSS(Knowledge organization,STRATORG:)
C00237 00041 .SSS(Character,STRATCHAR:)
C00245 00042 .FULLPAGEFIG
C00249 00043 .skip to line 1
C00252 00044 .SSS(Intellectual difficulty)
C00257 00045 .SSS(Overhead)
C00267 00046 .SS(Summary)
C00270 ENDMK
C⊗;
.S(Strategies, meta-rules for guidance);
.BEGINSMALLQUOTE;TURN ON "→";INDENT 0,0,0;
→Know that I have gone many ways wandering in thought.
.ENDSMALLQUOTE(|%2Oedipus the King%*, lines 66-67|)
.SS(Introduction);
.ind exhaustive invocation
In most existing performance programs, the largest number of
knowledge sources relevant to any one goal is small enough that exhaustive
invocation is still computationally feasible.∪∪Any piece of the system that
contributes some
task-specific bit of intelligence will be referred to as a knowledge source
(KS). That intelligence may be at the level of the programming language
(e.g., {PRLANG LISP} functions) might be some piece of domain-specific
information, or information at any other level on which we care to focus. The primary
concern here will be with KSs at the level of problem solving; in
particular, inference rules of the sort shown in {YONFIG RULE}. As is common,
the "bit" of intelligence will be referred to as a %2chunk%*. (Since
strategies contribute intelligence to the system, they are KSs as well.
For the sake of clarity, however, we use the term only in the context of
object-level KSs.)∪# In current (June
1978) versions of {SYSTM MYCIN}, for example, the largest number of rules
relevant to a particular goal is on the order of 50, and all are invoked.
It seems clear, however, that since the knowledge bases in such performance
programs may eventually grow quite large, exhaustive invocation will in
time prove too slow. It was in response to this that meta-rules were
developed, to embody strategic knowledge about reasoning and to supply a
mechanism for guiding the reasoning process.
Meta-rules are the third major form of meta-level knowledge to be
considered.∪∪The others were the rule models and data structure schemata.∪
They provide a way of expressing knowledge about the use of knowledge and
are discussed here as a framework for knowledge organization. This chapter
is divided into four main parts. The first, {YON1 WIAS},
gives a fairly general introduction to the concept of strategies and
considers their place in guiding program operation. The second part,
{YON1 STRATMR}, discusses the specifics of meta-rule structure and function and
examines their contribution to problem solving performance. The third,
{YON1 STRATBROADI}, explores possible implications that the current meta-rule
implementation might have on programming in general. The final part,
{YON1 STRATAX}, then offers a very general view of
strategies, describing a taxonomy of strategy types and discussing the
impact of each on the organization of knowledge in a program.
.SS(The main ideas,MAINIDEAS:);
Much of the utility and impact of meta-rules derives from a few
basic ideas. These are listed and described below, then developed more
fully in the remainder of this chapter.
.ind saturation
.BEGINQUOTE;
Almost all current problem-solving control structures are susceptible to
%2saturation%*, the situation in which so many applicable knowledge sources
are retrieved that it is unrealistic to consider nonselective, exhaustive
invocation.
.ENDQUOTE;
The issue of invocation, considered in the most general terms, is
a central theme for much of the work described in this chapter. Over the
years many different approaches to invocation have been developed,
including standard subroutine calling, varieties of pattern-directed
invocation, etc. An important characteristic of all but the most basic
scheme (subroutine calling) is that more than one knowledge source may be
retrieved for invocation. All invocation schemes with this property share
an important potential weakness, which we call %2saturation%*.
That is, given a sufficiently large knowledge base, so many knowledge
sources may be retrieved that it becomes impossible to invoke them all. In
that case some decision must be made about how to order and choose from that
set.
It was this issue that motivated the development of strategies
described here, and it is this issue of strategies as a source of guidance
in the face of control structure saturation that will provide much of the
focus for this chapter.
We also consider some extensions of this view and describe, first,
how strategies can provide useful guidance even when a program is not
immobilized by saturation. In this case, strategic
knowledge allows a program to proceed "more logically," without
necessarily affecting the program's final result. Second, we show how the
mechanism used to define strategies has interesting consequences, in terms
of allowing more than just invocation control; it allows a definition of
new invocation criteria as well.
.BEGINQUOTE;
We define a strategy to be information about which knowledge source(s) to
invoke when more than one is potentially useful.
.ENDQUOTE;
Strategies are thus one form of meta-level knowledge; specifically,
information about the use of object-level knowledge. This view provides a
useful perspective on the organization and use of knowledge in a program
and suggests an important site for embedding knowledge to improve
performance. We also show how this view can be generalized and consider
strategies as any information about how or when to apply
the various sources of object-level knowledge in a program.
.BEGINQUOTE;
Strategies can control invocation by "tuning" a control structure.
.ENDQUOTE;
Our initial application of strategies is in the context of a single control
structure and shows how to deal with potential saturation by "tuning"
the existing knowledge source invocation scheme.
.ind content-directed invocation
.BEGINQUOTE;
Meta-rules are implemented by a technique called %2content-directed
invocation%*, which has interesting implications as a knowledge source
retrieval mechanism.
.ENDQUOTE;
By %2content-directed invocation%*, we mean that meta-rules refer to
object-level rules by direct examination of the content of the object-level
rules. We compare this to more traditional retrieval mechanisms and
demonstrate its advantages with respect to ease of modification of the
program.
.BEGINQUOTE;
Problem-solving control structures can be viewed as use of different
retrieval criteria.
.ENDQUOTE;
For example, goal-directed invocation involves retrieving knowledge sources
by the goal they accomplish; data-directed invocation selects on the basis
of the data available; while means-ends analysis retrieves on the basis of
differences between the current state and the goal state.
.BEGINQUOTE;
Content-directed invocation provides an explicit, functional definition of
retrieval criteria and offers a mechanism for defining new criteria.
.ENDQUOTE;
&& thus provides an environment in which the retrieval criteria are not
predefined and embedded in the interpreter (as in most programming
languages) but are, instead, available to the programmer. We will see this
idea applied primarily in the context of tuning an existing control
structure. The idea is also considered briefly as the basis for a program that
adaptively selects its own control structures.
.SS(What is a strategy,WIAS:);
The word "strategy" has been used in many contexts and senses, and
seems to be a somewhat elusive concept. We are concerned here mainly with
its impact in the context of problem solving and offer a definition in
these terms.
To help set the context, we consider first a broadly construed view
of problem solving and examine the notion of ill structured problems.
.SSS(Ill structured problems, STRATISP:);
To characterize the class of problems most relevant to the
framework presented below, we consider the distinction between a
%2well structured%* and an %2ill structured%* problem. The former is
described in [[Newell69] as a problem:
.BEGINLIST;
(a)\which can be stated in terms of numerical variables,
(b)\whose goals can be specified in terms of a well-defined objective function, and
(c)\for which there exists an algorithmic solution.
.ENDLIST;
Ill structured problems are those which do not meet one or more of the
above conditions.∪∪Simon has argued [[Simon73] that the division
between well structured and ill structured problems is less precise and
that even problems meeting these criteria in principle may be ill structured
in practice. This is due to the unrealistic amount of computation required
to satisfy condition (c) above when a program's knowledge base is very
large.∪ The most general such case would lack even a definition of the
initial state and a specification of the goal. Most problems attacked by
AI, however, have well-defined initial and goal states; the third condition
is the one most often not met. Note that the domain of clinical medicine
is more ill structured than most since in many cases it is not certain
what constitutes the "correct" diagnosis (and hence therapy).
To illustrate this distinction between well structured and ill
structured problems, consider the task of the
{SYSTM STUDENT} program [[Bobrow68], which dealt with the domain of simple
algebra word problems. It first created equations that corresponded to
the natural language text, then solved those equations. The problem of
turning the natural language into a set of equations is highly
ill structured. Once the equations are determined, however, the process of
solving them is perfectly straightforward.
For purposes of this discussion we focus on the behavior displayed by
programs that attempt to solve ill structured problems. We examine, in
particular, the degree of nondeterminacy in the process of selecting a KS
to invoke, and show that the nondeterminacy present in ill structured problems
is a common source of saturation.
To see this, consider that well structured problems (like solving a
set of linear equations) can (by definition) be solved algorithmically.
Hence at each point of the problem solution there is no question about
which knowledge source should be invoked next and no question of whether
this invocation gets us closer to the solution. Since ill structured
problems lack algorithmic solutions, the choice of a KS to invoke is at
best a good guess. In such a case, we may be faced with a problem for which
.BEGINLIST;
(a)\it may be useful to make explicit in the program the process by which a KS is
selected (as opposed to the situation in algorithmic programs, where only
the end result of the selection process is evident, in the predefined
sequence of KS invocations);
.SKIP 1;
(b)\the result of the selection process may be a number of KSs, all of which
are potentially useful (as opposed to the single KS [pre]selected for
invocation at each step of an algorithmic program); and
.SKIP 1;
(c)\the process of selecting a KS for invocation needs to be
carried out often (i.e., invocation of a particular KS does not carry
the computation very far, and many such invocations are needed before reaching
a solution).
.ENDLIST;
As will become clear in the remainder of this chapter, all of these
were important considerations in the concept and design of meta-rules. At
the moment, however, it is useful to focus on the second, since it
leads us back to the idea of saturation. That is, one important cause of
saturation is the nondeterminism present in ill structured problems.
When ill structured problems are attacked with the production
system methodology, the concept of "degree of nondeterminacy" has a
.ind conflict set
well-specified instantiation:# It is called the %2conflict set%*. This is the set
of all rules that, at any given moment, meet the tests for applicability
and, hence, could justifiably be used. Depending on the nature of the
problem, the conflict set may range from a single rule to every rule in the
system.
It will be useful to generalize this concept slightly so that it
will be applicable to additional programming methodologies. Rather than the
.ind plausible knowledge source set
conflict set, we will speak of the %2plausible knowledge source set%* (PKS
set) and mean by that the set of all KSs that, at some given moment, are
plausibly useful and appropriate to invoke. This will also serve to emphasize
that saturation is independent of any specific knowledge
representation or control structure. Any system, faced with a sufficiently
ill structured problem and a large enough knowledge base, may be unable to
select out few enough KSs to make exhaustive invocation feasible.
By defining two averages on this set, we can construct a more
quantitative interpretation of the concept of well structured and
ill structured problems. The "average size" of the PKS set will be defined
as a time average of its size over the course of the entire problem
solution. The "average power" will be defined as the average of the power
of each of its members.∪∪"Power" is the concept defined by Newell
[[Newell69] as "the ability to deliver solutions."# He describes it as
composed of (among other things):# a KS's probability of finding a solution,
the quality of the solution (optimal, or how suboptimal), and the computational
expense incurred in invoking the KS.∪
The "degree of ill-structuredness" of a problem should then be
directly proportional to the average size of the PKS set and inversely
proportional to its average power. (This is of course a relative rather than
absolute scale, whose utility lies in making broad comparisons rather than
independent measurements.)## If this number is relatively small, the problem
is more likely to be well structured and not the type of problem we will
be considering here. The larger this number gets, the more relevant the
remainder of this analysis becomes.
.SSS(Strategies,STRATDEF:);
With this background we can now examine the notion of strategy in
more detail. We present three successively more general views, beginning
with a definition in terms of coping with saturation.
.SSSS(Strategies as a response to saturation);
Faced with a PKS set of nontrivial size and a desire to avoid
blind, exhaustive invocation, some decision must be made about which KS
should be the next to be invoked. It is our contention that this decision
point is an important site for the embedding of knowledge, because system
performance will be strongly influenced by the intelligence with which the
decision is made. We claim also that it is a decision which in many systems
is made on the basis of knowledge that is neither explicit, nor well
organized, nor considered in appropriate generality.
We take this as a starting point and offer our initial definition
of strategy in terms of it:# We suggest that a strategy can profitably be
viewed as %2information concerning which chunk of knowledge might be invoked
next, when more than one chunk may be applicable%*.
The utility of this view of strategies
arises from its applicability both to
problem solving (in particular, for ill structured problems) and to current
developments in programming languages. Invocation in traditional (i.e.,
{PRLANG ALGOL}-like) programs, for example, is "well specified," in the
sense that only one procedure is considered for invocation at any given
moment. Many of the programming paradigms developed more recently,
however, admit (or even encourage) the possibility of retrieving several
chunks of knowledge, all of which are plausibly useful in a single
situation (e.g., this is true for production rules, {PRLANG PLANNER}-like
languages, as well as other languages with choice-point and backtracking
mechanisms). Typically, in these paradigms, the KSs are retrieved
unordered and are invoked exhaustively, each considered in turn, until some
stopping criterion is met or until all have been tried. However, faced
with a set of alternatives large enough (or varied enough) that blind,
exhaustive invocation would be infeasible, some decision must be made about
which should be chosen.∪∪A few of the paradigms offer mechanisms for doing
this. For example, the concept of %2conflict resolution%* used with
production rules offers a limited means of ordering the KSs retrieved, but
its use thus far has been purely syntactic. It may, for instance, order
rules based on which of those retrieved was used least recently. As we
will see, {PRLANG PLANNER}'s %ATHUSE%* and %ATHTBF%* mechanisms are
somewhat more sophisticated.∪# The concept of strategy thus appears to
have a natural place in considering questions of programming language design
as well as problem solving.
.SSSS(Strategies as meta-level knowledge,STRATASMLK:);
Considered in more general
terms, strategies are a third example of meta-level knowledge, in
particular, knowledge about how (and when) to use the various sources of
object-level knowledge.
To illustrate this concept and emphasize that it is widely
applicable, three common approaches to problem solving are listed below,
along with examples of object-level and meta-level knowledge for each. In
each case, the meta-level knowledge consists of advice about how and when
to use the various sources of object-level knowledge.
.GROUP;
.BEGINLIST;
(a)\Problem decomposition:
.ENDLIST;
.SKIP 1;
%2object level%*--knowing how to decompose the problem (i.e., knowing what the necessary and sufficient
subgoals are),
.SKIP 1;
%2meta level%*--knowing how to order the attack on the subgoals for
efficiency (i.e., knowing which
of several possible decompositions to try);
.APART;
.SKIP 2;
.GROUP;
.BEGINLIST;
(b)\Cooperating knowledge sources:
.ENDLIST;
.SKIP;
%2object level%*--the domain knowledge contained in the various sources,
.SKIP 1;
%2meta level%*--knowing which knowledge source to use at each point in solving the problem;
.APART;
.SKIP 2;
.GROUP;
.BEGINLIST;
(c)\Heuristic search:
.ENDLIST;
.SKIP 1;
%2object level%*--knowledge of the search space (e.g., for game playing, a legal
move generator and other operations on the domain primitives),
.SKIP 1;
%2meta level%*--the various search strategies (alpha-beta, branch and bound, hill climbing, etc.).
.APART;
.skip
.continue
To emphasize the generality issue, consider the concept of
the PKS set, defined as all KSs that are "plausibly useful."# What in
fact constitutes "plausibly useful"? For the vast majority of systems, the
answer is assumed to be obvious--in production systems and
{PRLANG PLANNER}-like languages, for instance, it is based on pattern
matching and, after all, it's "obvious" when a pattern matches. Such knowledge
is thus often buried deep within a system (if it is represented explicitly at
all), and indeed the {PRLANG PLANNER} pattern matcher operates at a very low
level, compared with other features of the language. We claim, however, that
even this chunk of knowledge should be regarded as a strategy and should be
made explicit in the system.
.ind flexibility
Among the advantages would be flexibility.
For example, in an event-driven system using pattern-directed invocation of
KSs (e.g., {PRLANG PLANNER} antecedent theorems), only a certain subset
of the KSs are considered--those with patterns containing obvious
discrepancies with current information are ignored. Consider, however, the
utility of checking for misinterpreted or missing data in a noisy domain in
the following way:# If several strategies indicated strongly that a certain KS
would be useful, but its pattern doesn't currently match, it may be useful
to retrieve that KS nevertheless. The discrepancies between this KS and the current
data base might in fact be a useful hint about where to check for missing or
misinterpreted data. Thus, by turning this "obvious" chunk of
knowledge--defining what it means to "match"--into an explicit strategy, we obtain a
highly flexible system, one that can be "tuned" to account for the degree of
noise in the domain with relatively little trouble. Fundamental changes in system
performance can therefore be controlled at a fairly high level.
Note that this view makes few assumptions concerning
the underlying methodology. It appears to be a useful perspective over a range
of representation techniques. It describes equally well, for example, the
organization of knowledge for systems that are event driven as well as those
that are goal directed. In the former case, the question is how to select the
most relevant subset from all the potential implications of a new event; in the
latter it becomes the intelligent choice of a KS that helps achieve the current
goal.
.SSSS(Strategies as a means of defining and choosing invocation criteria);
Finally, strategies are also traditionally viewed as a kind of
"fine-tuning" of a general method; as, for example, set-of-support is used
to improve the performance of resolution theorem proving. As will become
clear below, however, we need not restrict ourselves to this view. In the
most general terms, we can view strategic knowledge as any decision
concerning how or which knowledge to use. Adopting this view will make it
clear that strategies need not be set in the context of tuning a single
method but can more generally be used to choose (or even define) the method
itself. This view is developed further in {YON1 STRATBROADI}.
.SSS(Levels of knowledge);
.ind levels of knowledge
The discussion thus far has suggested the existence of only two
levels of knowledge, the object and meta levels. It seems plausible,
however, to continue this sequence through an arbitrary number of
levels. Where strategies direct the use of object-level knowledge, second
order strategies direct the use of strategies (e.g., when is hill climbing
better than branch and bound), third order strategies suggest the criteria
for choosing strategies (e.g., how do I go about deciding which search
technique is the best), and so forth. Note that the process is the same at
all levels; each level directs the use of the knowledge at the next lower
level.∪∪This hierarchy is analogous to the one in chapter 6 labeled
"levels of generality."##In both cases, each higher level describes
knowledge at the next lower level. Each level of the hierarchy
discussed in chapter 6
(instance, schema, schema-schema) describes the
%2representation%* of knowledge at the next lower level; here, each level of
strategy describes the %2use%* of knowledge at the next lower level.
However, while the hierarchy of chapter 6 appears to end at the third
level, here there appears to be no #a#priori limit to the number of
levels.∪
Part of the intuitive appeal of the higher levels of strategy lies
in the belief that the invocation of a useful piece of strategy knowledge
at a high level offers advantages similar to choosing an appropriate branch
early in the search of a large tree. That is, since the strategy at level
N selects the relevant strategies at level N-1, and since this carefully chosen
subset of strategies does the same for the strategies at level N-2, etc.,
the strategy at level N can exert a powerful focusing influence on the
whole process.
Two global considerations are relevant here. First, the domain
must allow successive levels of strategies. It is not
obvious, for instance, what some of the fourth and higher level strategies
would look like, even for familiar methodologies like heuristic search. The
domain should thus be sufficiently formalized that it is possible to
determine the conceptual primitives of each level of knowledge.
Second, these strategies must be effective, that is, the result of
invoking any one level of strategy must be a useful selection of knowledge
at the next lower level. This means that some fairly specific statements
can be made about useful choices at each level.
In what follows, for the sake of exposition, most issues are
discussed as if there were only two levels, but they can be generalized to
an arbitrary number of levels.
By combining the concept of multiple levels with the view of the
nature of strategic knowledge suggested earlier, we see the beginning of a
general framework for the organization and explication of strategy
knowledge. The selection of a methodology (like the ones in
{YON3 STRATASMLK}) might for instance be accomplished by a hierarchical set of
strategies which decide, first, %2how to choose%* a methodology (second order
strategy) and then %2which methodology%* to choose (first-order). As
before, the selection of a particular methodology may then imply further
decisions to be made that would once again be the task of
strategic knowledge.
While writing strategies can involve a significant amount of
effort, even a moderate investment appears to pay off quite well. Certain
aspects of the organization of the {SYSTM HEARSAY II} system, for example,
can be viewed in light of successive levels of knowledge,
demonstrating the power of the technique. That system is built around a large
number of demons, each waiting to fire and contribute its chunk of
knowledge. Each demon has a set of arbitrarily complex preconditions which
specify the circumstances necessary for it to be relevant. But it would be
prohibitively expensive to evaluate all implicated
preconditions every time a new datum enters the data base. In order to
avoid this, the precondition of each demon has its own precondition (the
"pre-precondition"), which specifies the general conditions under which the
system should bother to evaluate the whole precondition. Apparently
even these two levels of knowledge are sufficiently powerful to support
acceptable performance.
.SSS(|Building blocks:# Conceptual primitives, language|, STRATBB:);
Object-level knowledge is built from conceptual primitives
specific to the domain of application. In {SYSTM MYCIN}, for
instance, the notions of organism gramstain, morphology, and identity are
relevant concepts. Object-level primitives thus characterize the domain, and it
is the search for an appropriate set of them, and a language in which to express
and use them, that is a large part of the traditional representation problem of
AI.
Strategies, on the other hand, require conceptual primitives that
describe characteristics of knowledge rather than characteristics of the
domain. Some of those primitives might deal with general attributes of
a KS like:
.BEGINLIST
(a)\preconditions for its use--to assure its utility,
.BREAK
(b)\any side effects--to make clear all the implications of using it,
.BREAK
(c)\its main effect--so that it can be used when relevant, and
.BREAK
(d)\the main factors on which it is based--a finer degree of characterization than main effect.
.ENDLIST;
Others might be suggested by the structure of the object-level
primitives. For instance, as noted earlier, the current performance
program uses both consequent and antecedent rules; each rule is composed of
a premise and an action; these, in turn, are made up of clauses; and the
clauses are built from predicate functions, attributes, objects, values,
certainty factors, etc. Each of these suggests several possible meta-level
primitives:# Is the rule an antecedent or consequent rule? How many premise
clauses are there? Which functions, attributes, etc., does the rule employ?
Is the certainty factor positive or negative? etc. In the same way,
the components of any sort of KS could provide hints about potentially
useful primitives for characterizing it.
A suitably large set of such primitives would form the basis for a useful
%2strategy language%*. More is of course needed:# It is not enough just to
choose the primitives; there must be a way of expressing, combining, and
using them, so as to effectively direct the use of object-level knowledge.
Since there are many advantages to be gained by a uniform encoding of
knowledge, it is useful if the object-level syntax can simply be augmented
with the new meta-level primitives to provide the strategy language. A
demonstration of this technique and a discussion of its advantages is given
below.
While this view has indicated where to find a useful subset of
meta-level primitives, the question of determining the entire collection
may be a good deal harder. We claim below that the set is at least very
large, and perhaps open-ended. These claims are, in turn, important
considerations for the design of a strategy representation and are
discussed in {YON2 STRATFLEX}.
.SKIP TO LINE 1;SS(Meta-rules, STRATMR:);
As noted, the initial motivation for meta-rules was to provide a
mechanism to guide the performance program
faced with saturation. This section discusses issues of meta-rule
design and representation primarily in that light. It also considers
additional applications for meta-rules and demonstrates their utility in a
variety of contexts. Shortcomings of the current implementation are also
reviewed.
.SSS(Format);
Two examples of meta-rules are shown below, in both the internal
format and the English translation that results.∪∪For reasons noted in
chapter 1, the translation is somewhat awkward; these particular rules
suffer especially from the clause-by-clause approach to translation.∪
.STARTFIG;
∪METARULE001
If 1) the culture was not obtained from a sterile source, and
2) there are rules which mention in their premise a
previous organism which may be the same as the current
organism
Then it is definite (1.0) that each of them is not going to be
useful.
PREMISE: ($AND(NOTSAME CNTXT STERILESOURCE)
(THEREARE OBJRULES
(MENTIONS CNTXT PREMISE SAMEBUG) SET1))
ACTION: (CONCLUDE SET1 UTILITY NO TALLY 1.0)
.APART;
.GROUP;
∪METARULE002
If 1) the infection is a pelvic-abscess, and
2) there are rules which mention in their conclusion
enterobacteriaceae, and
3) there are rules which mention in their conclusion
grampos-rods,
There is suggestive evidence (.4) that the former should be
done before the latter.
PREMISE: ($AND (SAME CNTXT PELVIC-ABSCESS)
(THEREARE OBJRULES(MENTIONS CNTXT ACTION
ENTEROBACTERIACEAE) SET1)
(THEREARE OBJRULES(MENTIONS CNTXT ACTION
GRAMPOS-RODS) SET2))
ACTION: (CONCLUDE SET1 DOBEFORE SET2 TALLY .4)
.FIG(Meta-rule examples,METARULES:);
.ENDFIG;CONTINUE;
The strategic impact of the first rule arises from the fact that an old
infection which has been cured only temporarily may recur, perhaps as much
as a month later. Thus, one of the possible ways to deduce the identity of
a current organism is by reference to previous infections. However, this
line of reasoning is not valid if the current infection was cultured in a
fashion that caused the sample to be nonsterile (e.g., taken from a
nonsterile site). Thus the rule, in effect, says %2if the current culture
is not from a sterile source, don't bother trying to deduce the current
organism identity from the identity of previous organisms%*. As should be
clear, this is a global statement about how to reason in a given situation
and as such offers a useful piece of strategic advice.
The second rule indicates that since enterobacteriaceae are
commonly associated with a pelvic abscess, it is a good idea to try rules
concluding about them first, before the less likely grampositive rods.
The syntax for meta-rules is identical to object-rule syntax,
extended to include two new predicate functions (%AMENTIONS%* and its
complement, %ADOESNTMENTION%*), and two new attributes (which concern a
rule's %AUTILITY%* and its place in the sequence of rules to be invoked
(%ADOBEFORE%*)). Two important benefits accrue from using a single syntax:#
First, meta-rules may employ all the existing machinery of certainty
factors to make inexact statements, and, second, the system has a uniform
encoding of all levels of knowledge. Implications of these are
discussed below.
The current implementation has a very simple syntax but offers a
useful range of expression. Meta-rules can indicate:
.STARTFIG;TURN OFF "{";
%1(a) the utility of object-level rules (as in METARULE001):%A
under conditions A and B,
rules which do {not} mention X in their {premise
action}
will {definitely be useless
probably be useless
...
probably be especially useful
definitely be especially useful}
.APART
.GROUP;
%1(b) a partial ordering of the object-level rules (as in METARULE002):%A
under conditions A and B,
rules which do {not} mention X in their {premise
action}
should {definitely be used {first.
probably last.
... before
possibly} after}
rules which do {not} mention Y in their {premise
action}
.ENDFIG;
Note that the primitives that have been added to the syntax deal,
as expected, with characteristics of knowledge. For example, the new predicate
functions are based on the fact that the knowledge representation is a composite
structure whose components are accessible; hence, it makes sense to refer to the
content of a rule. The new attributes are based on the recognition, first, that
a rule invocation is a discrete event, so it makes sense to indicate order; and,
second, that one rule may be more useful than another, so we can talk
meaningfully about utility.
These simple additions allow the statement of the fairly broad range of
strategies indicated above and have so far met all current needs.
.SSS(Function);
We present first a simplified picture of meta-rule function and
elaborate on it in several stages. In the simplest case, meta-rules (like
object-level rules) are associated with an attribute. As explained in
chapter 2, during the course of attempting to establish the value of any
attribute, the system retrieves the list of rules relevant to that
attribute. Before any of these rules is invoked, however, the system
checks for meta-rules associated with the same attribute. If there are
any, these are executed first and act to reorder or prune the list of
object-level rules (thereby guiding the system's search through the goal
tree). The modified list is then passed to the standard rule interpreter
described in chapter 2.
There is no reason to constrain this process
to a single level of strategies, and the current implementation is general
is this respect. If first-order meta-rules are present, the process
recurs, and second-order rules are sought, which would then be used to reorder
or select from the first-order list, and so on.∪∪We have not as yet
uncovered any second or higher order meta-rules, but then neither have we
actively looked for them. In general, meta-rules have offered more expressive
power than we have yet been able to use.∪ Recursion stops when there is no
rule set of the next higher order, and the process unwinds, allowing each
level of knowledge to direct the use of the next lower level.
Meta-rules may also be written to control the invocation of
object-level antecedent rules. When a conclusion is made, the system
retrieves the list of antecedent rules associated with that conclusion. If
the list is not empty, the system checks for the existence of applicable
meta-rules (i.e., meta-rules associated with the antecedent rules dealing with
that conclusion) and allows them to reorder or prune the list of
conclusions to be made. This provides a mechanism for writing strategies to
control the depth and breadth of implications drawn from any new fact or
conclusion.
.SSSS(Details,STRATMRDETAILS:);
Meta-rules operate by making conclusions about the utility and
relative ordering for each object-level rule. To see how this is
done, consider the invocation of the two meta-rules shown earlier in
{YONFIG METARULES}.
Assume the system is attempting to determine the identity of an
organism. It will retrieve the list of all object-level rules concluding about
identity (call the list L) and then the list of meta-rules associated with
identity. Assume the process ends here because there are no second-order
meta-rules and that the first meta-rule in the list is %AMETARULE001%*. If the
culture under consideration is not from a sterile source, the first clause
succeeds. Evaluation of the second clause
.STARTCENTERIT(A);
(THEREARE OBJRULES(MENTIONS CNTXT PREMISE SAMEBUG) SET1))
.ENDCENTERIT;
results in assigning to %ASET1%* the subset of rules that mention "a
previous organism with possibly the same identity as the current organism"
(%ASAMEBUG%*).
Note that determining the appropriate subset of object-level rules
is accomplished by direct examination of the code of the object-level
rules. That is, each of the rules in L is tested by the function
%AMENTIONS%*, which examines the source code of the rule to see (in this
case) if that rule mentions the attribute %ASAMEBUG%* in its %APREMISE%*.
(Implications of this direct examination of source code--which we call
%2content-directed invocation%*--are explored below in {YON1 STRATBROADI}.)
The action part of %AMETARULE001%* then concludes that each is
definitely not useful.
Evaluating %AMETARULE002%* proceeds analogously: If the patient is a
compromised host, %ASET1%* is assigned the list of all rules mentioning the
identity pseudomonas, %ASET2%* is assigned all rules mentioning klebsiella. The
conclusion would then indicate that there is "suggestive evidence" that
each rule in %ASET1%* should be done before any of those in %ASET2%*. This
employs all the pre-existing certainty factor machinery, allowing the
curious ability to make inexact statements about the order of a sequence of
events.∪∪By phrasing the rule correctly, %ADOBEFORE%* can be used to state
four different relationships:# "Do list X before list Y" and "do list X
after list Y" are handled in the obvious way; "do X last" means "do
complement-X before X," and "do X first" means "do X before complement-X."∪
When all the meta-rules have been applied, they will have made a
number of conclusions about the utility and relative order of the rules in
L. The task now is to sort and perhaps prune L, based on those conclusions.
Since the transitivity of the order relation often introduces constraints
that are not explicitly mentioned by a meta-rule,∪∪For instance, if "do X
before Y" and "do Y before Z" are indicated by rules, often there is no
rule that indicates the necessary condition of "do X before Z."∪ it is
first necessary to compute the transitive closure of the set of ordering
constraints. A straightforward implementation of Warshall's algorithm
[[Warshall62] supplies this.
The pruning of L is prompted by conclusions like those in
{YONFIG METARULES}, which indicate that some rules will definitely be useless
and hence can be deleted. For the remainder, the most useful rules should be
tried first.
The final step is thus a sort-and-delete pass through L using the
following criteria:
.STARTFIG;
If the utility of a rule is -1, delete it from L, otherwise
rule X goes before rule Y if
it is required by ordering constraints, or
the utility of X is higher than the utility of Y
.ENDFIG;CONTINUE;
The result is a reordered and possibly shortened list.
Note that with exhaustive search of the goal tree, order will make
a difference in the final answer only if the system happens to encounter a
rule with #CF#=#1.0# that executes successfully, since in that case search is
terminated. Even if the final answer is unchanged, however, the program's
performance may appear more rational as a result of reordering the rules,
since it will then try the more "appropriate" lines of reasoning first.
{YON2 STRATFUTWORK} considers the potential impact of this form of
meta-rule if search is not exhaustive.
Note also that even though utility and rule order
are both eventually used to sort the
list, they are maintained as independent factors, since they
represent two different kinds of judgments. To see this, consider that it
might, for example, be possible to conclude that two rules are definitely
(CF#=#1) going to be especially useful; yet independent considerations
might still indicate that one of them should be invoked before the other.
The entire process is summarized below (simplified by assuming that there
is only one level of meta-rules):
.STARTFIG;
To deduce the value of an attribute A:
1) L ← the list of rules which conclude about A
2) L' ← the list of meta-rules associated with A
3) Evaluate each of the rules in L'; this may result in some
conclusions about the rules in L
4) Sort and prune L according to the criteria shown above
5) Evaluate each of the rules in L; this may result in
conclusions about the value of A
.ENDFIG;
.SSS(Implications of meta-rules as a strategy encoding);
There are several advantages to this approach to encoding
strategies. To make these advantages clear, recall that the basic
control structure of the performance program is a depth-first search of the
and/or goal tree sprouted by unwinding rules.
The first advantage arises from the significant leverage
apparently available from the addition of a store of (meta-level)
knowledge describing which chunk of object-level knowledge to invoke
next. Considered again in tree search terms, we are talking about the difference
between "blind" search of the tree and one guided by heuristics. The
advantage of even a few good heuristics in cutting down the combinatorial
explosion of tree search is well known.
Consider, too, that part of the definition of intelligence includes
appropriate use of information. Even if a store of (object-level)
information is not large, it is important to be able to use it properly.
Meta-rules provide a mechanism for encoding strategies that can offer
additional guidance to the system.
Third, the presence of meta-rules associated with individual attributes
(as the rule in {YONFIG METARULES} is associated with the attribute
%AIDENT%*ity) means that this goal tree has an interesting characteristic:# At
each node, when the system has to choose a path, there may be information
stored advising about the best path to take. There may therefore be
available an extensive body of knowledge to guide the search, but this
.ind search algorithm
knowledge is not embedded in the code of a clever search algorithm. It is
instead organized around the specific objects that form the nodes in the
tree; that is, instead of a smart algorithm, we have a "smart tree."
.ind smart tree
The power in using rules to guide rules applies at multiple levels
as well:# There is leverage in encoding heuristics that guide the use of
heuristics. Thus, rather than adding more heuristics to improve
performance, we might add more information at the next higher level
concerning the effective use of existing heuristics.
Fourth, note that the rules can be judgmental. This makes it
possible to write rules which make different conclusions about the best
strategy to use, and then allows the underlying model of confirmation to
weigh the evidence. That is, the strategies can "argue" about the best
rule to use, and the strategy that presents the best case (as judged
by the confirmation model) will win out.
The judgmental character also allows the novel possibility of both
inexact and conflicting statements concerning relative order. We might,
for instance, have two meta-rules that offer different opinions about the
order of two sorts of object-level rules, indicating that there is evidence
that "subset X should probably (.6) be done before subset Y" and that
"subset Y should probably (.4) be done before subset X."# Once again, the
underlying model of confirmation will weigh the evidence and produce an
answer.∪∪Note that there is, in general, no logical contradiction in the
concurrent existence of evidence suggesting both orderings. Only one case
is contradictory: In the current model it would be contradictory to have
definite evidence (CF = 1) for both the "before" and "after" orderings.
The implementation of meta-rules does not now check for this case, but it
should someday be upgraded to do so.∪
Next, there are several advantages associated with the use of
strategies that are goal-specific and are embedded in a representation
that is the same as that of the object-level knowledge. The fact that
strategies are %2goal-specific%*, for instance, makes it possible to
specify quite precise heuristics for a given goal, without imposing any
overhead in the search for any other goals. That is, there may be a number
of complex heuristics describing the best rules to use for a particular
goal, but these will cause no computational overhead except in the search
for that goal.
Finally, the use of a %2uniform encoding of knowledge%* makes the treatment
of all levels of knowledge the same, and this offers several advantages.
For example, our work on explanation (chapter 3) and knowledge acquisition
(chapter 5) for object-level rules can, as a result of the uniform
encoding, easily be extended to meta-rules as well. The first of these
(explanation) has been done and makes possible an interesting capability:#
In addition to being able to display the object-level rules used during a
consultation, the system can similarly display the meta-rules, thereby
making visible the criteria it used in "deciding how to do what it did"
(see {YON2 STRATEXPLACQ}). Knowledge in the strategies has become
accessible to the rest of the system and can be displayed in the same
fashion.
Additional advantages associated with making strategies
explicit are described in {YON3 STRATGIC}.
.SSS(Advanced issues,stratadviss:);
For the sake of clarity, the description of meta-rule operation
given above omitted some details of knowledge organization. These details
and their implications are examined below.
Experience with the meta-rule construct has also indicated
that it is a convenient mechanism for encoding forms of knowledge in
addition to those described above. Two such uses are discussed below,
demonstrating that it is possible to embody in meta-rules a limited subset
of the knowledge formerly embedded (sometimes quite subtly) in the
performance program. These two types of rules either capture aspects of
the control structure or make explicit what we refer to as "design
decisions."
Some of the material presented here relies on some fairly specific
(and occasionally subtle) aspects of the present performance program's
organization. It is thus not as widely relevant as preceding material and
is susceptible to change as experience with it increases.
.SSSS(Meta-rule organization:# Static);
It was indicated earlier that meta-rules, like object-level rules,
are associated with specific attributes. It is also possible to associate
a meta-rule with any of the objects (e.g., an infection, culture, organism,
etc.). In that case, the rule is used as a strategy for all attributes of
that object and for all attributes of any object that gets sprouted below
it.∪∪Recall that objects are organized into a tree of the sort shown in
{YONFIG OBJECTTREE}.∪ This offers the opportunity to state strategies whose
range of applicability runs from a single object (if associated with a
leaf of the object tree) to the entire domain (if associated with the
root of the tree--domain-independent strategies are stored there). The
specificity of application of a strategy is thus controllable by choosing
the proper node in the object tree.
.SSSS(Meta-rule organization:# Dynamic);
Previous examples have illustrated two different forms of
meta-rules. The first meta-rule in {YONFIG METARULES} concluded about the
%2individual%* utility of a single object-level rule, while the second
meta-rule described the %2comparative%* utility of two classes of rules.
In terms of the tree search process that meta-rules guide, these two
examples deal with different criteria for ordering the paths to be
explored, based on a "look ahead" one level deep. It is also possible to
express some very simple strategies that use a look-ahead several levels
.ind line of reasoning
deep, to select a particular "line of reasoning."
A standard problem in doing this is the question of how deep in the
line of reasoning to explore or, in our terms, how long a sequence of rules
to consider. The longer the sequence, the more effective the choice may
be; but more work is involved in simulating the rule retrieval mechanism to
effect the look-ahead.
We have sidestepped the issue of how deep to look (and settled for
a weaker solution) by implementing a "line-of-reasoning" type meta-rule that functions
in a somewhat backward fashion. Each time the system tries to establish
the value of an attribute, it retrieves not only the meta-rules associated
with that attribute but any associated with any attribute higher in the
current chain of goals. Thus, instead of looking deeper from a node, each
node "looks up."## The combined set of meta-rules is used to reorder or
prune the current list of object rules.
In simpler terms:# The current implementation is functionally
equivalent to (but more efficient than) taking each line-of-reasoning type
meta-rule and putting copies at each node of the subtree to which it
applies. Thus, instead of having the system actively search ahead more than
one level, the relevant strategy is "brought down" the tree during the
normal search process.
The solution is weaker because it is "hardwired" into the depth-first
search used by the performance program and because it only searches one
level ahead. A true line-of-reasoning strategy would require the ability to do
its own examination of the search tree to an arbitrary number of levels.
There are thus several potential sources of meta-rules for any
given attribute. They may be associated with:
.BEGINLIST;
(a)\the attribute itself,
(b)\the object to which that attribute applies,
(c)\any ancestor of that object, or
(d)\any other attribute higher in the current chain of goals.
.ENDLIST;
Note that the scope of the first three of these is fixed but that the
last is established dynamically as the consultation proceeds.
.SSSS(Encoding control structure information,STRATCSINFO:);
There are object-level rules in the system that mention the same
attribute in their premise as they do in their actions. For example
(paraphrasing):# %2If you think the identity of the organism is pseudomonas,
and the patient has skin lesions, then that's strong additional evidence
that the identity is in fact pseudomonas.%* Such rules are referred to as
"self-referencing."# The current certainty factor model requires that all
the non-self-referencing rules be invoked before those which are
self-referencing. (Failure to do so would eliminate the commutative
property of certainty factors, and the final result might be dependent on
the order in which rules were invoked.)
In very early versions of the system, the mechanism that insured
this partial ordering was a heavily recursive, rather obscure piece of
code. It was not at all obvious what its purpose was, nor that this
restriction on rule order existed. A later version included a separate
function that did a straightforward reordering of the rule list just
before it was invoked. This at least made fairly obvious what was
happening and indicated explicitly what the ordering constraint was.
Embedding this constraint in a meta-rule ({YONFIG SREFMETARULE}) represents
a step toward a totally explicit, accessible chunk of knowledge. The
constraint is now quite clear, can be explained to the user by the system
itself (using the explanation capabilities outlined in chapter 3), and
can be modified (if necessary) by editing the rule.∪∪There was actually an
intermediate solution which illustrates the standard conflict between
efficiency and comprehensibility. When it was agreed that changes to the
knowledge base would not be made while a consultation was in
progress, it became possible to meet the constraint by pre-setting the
order of each internal list of rules by hand and keeping them stored in
that order. This eliminates all execution time overhead, but also means
that all representation of the constraint has disappeared from the system.∪
.STARTFIG;
∪METARULE003
If 1) there are rules which do not mention the current goal in
their premise
2) there are rules which mention the current goal in their
premise
Then it is definite that the former should be done before the
latter.
PREMISE: ($AND(THEREARE OBJRULES($AND (DOESNTMENTION FREEVAR
ACTION CURGOAL)) SET1)
(THEREARE OBJRULES($AND (MENTIONS FREEVAR PREMISE
CURGOAL) SET2))
ACTION: (CONCLUDE SET1 DOBEFORE SET2 1000)
.FIG(Example of a control structure meta-rule,SREFMETARULE:);
.ENDFIG;
.continue
A part of the rule interpreter has itself been encoded
in rule form. It may prove possible to express additional parts of the control
structure in meta-rules. Each time this is accomplished it means that some
additional element of the system's behavior becomes accessible and, hence, can be
explained or modified using the existing facilities.
.SSSS(Encoding design decision information);
For the sake of human engineering, it makes good sense during an
infectious disease consultation to ask about positive cultures (those which
displayed bacterial growth) before those that turned up negative.
Originally, this decision was embedded quite subtly in the ordering of a
list internal to the system code. It can be stated easily in a meta-rule,
however, as shown in {YONFIG DDMETARULE}.
.STARTFIG;
∪METARULE004
If 1) there are rules which are relevant to positive cultures,
and
2) there are rules which are relevant to negative cultures
Then it is definite that the former should be done before the
latter.
PREMISE: ($AND(THEREARE OBJRULES ($AND (APPLIESTO FREEVAR
POSCUL)) SET1)
(THEREARE OBJRULES ($AND (APPLIESTO FREEVAR
NEGCUL)) SET2))
ACTION: (CONCLUDE SET1 DOBEFORE SET2 1000)
.FIG(Example of a design decision meta-rule,DDMETARULE:);
.ENDFIG;
Such decisions, based on human engineering, are common in
user-oriented systems. Expressing this information in a rule renders it
explicit and accessible, making possible its explanation and modification.
In summary, since meta-rules act by pruning or reordering
the list of rules to be invoked, they can be used to express any part
of the control structure or the design decisions that can be understood in
those terms.
.SSS(Explanation and acquisition,STRATEXPLACQ:);
.IND explaining meta-rules
One important advantage of a uniform encoding of different levels of
knowledge is the ability to use a single set of facilities for all levels. In
the case of explanation, for instance, all the machinery described earlier
that deals with object-level rules can be employed to deal with meta-rules. To
do this, it
proved necessary to make only two small extensions, augmenting the existing record
of rule invocations to include meta-rules and providing the natural language
facilities for explaining the meta-rule's contribution to program performance.
An example of the capability that resulted is shown in a consultation segment below.
(Because %AMETARULE001%* refers to culture source, which is already known when
the rule is invoked, it does not normally generate any questions and is thus
transparent to the user. For the sake of illustration, the first clause has
been changed to one that does generate a question, giving the user an
opportunity to request
an explanation.)
.STARTFIG;APART;
--------ORGANISM-1--------
10) Enter the identity of ORGANISM-1:
**%3UNK%A
11) Is ORGANISM-1 a rod or coccus (etc.):
**%3ROD%A
12) The gram stain of ORGANISM-1:
**%3NEG%A
13) Do you consider George Filbert to be a compromised host
(alcoholic, immunosuppressed, etc.)?
**%3WHY%A
[i.e. WHY is it important to determine whether or not PATIENT-4
is a compromised host?]
[1.0] This will help determine a strategy for deducing the
identity of ORGANISM-1.
If
[1.1] the patient is a compromised host, and
[1.2] there are rules which mention in their premise a
previous organism which may be the same as the current
organism,
then
It is definite (1.0) that each of them is not going to be
useful.
[METARULE001]
**%3HOW [1.0]%A
[i.e. HOW was the strategy for deducing the identity of
ORGANISM-1 determined?]
At that point METARULE001 was being used.
In addition, the following were also used:
[1.3] METARULE003 indicated it is definite that the former
should be done before the latter
.STARTCOM;
{Due to the primitive approach to natural language, rule translation can be a
bit cryptic at times. However, see below, where the full rule text makes things
a little clearer.}
.ENDCOM;
**%3HOW [1.3]%A
[i.e. HOW was METARULE003 used?]
If [2.1] there are rules which do not mention the current goal
in their premise, and
[2.2] there are rules which mention the current goal in
their premise
Then it is definite that the former should be done before the
latter.
[METARULE003]
.ENDFIG
We have not yet attempted the interactive acquisition of
meta-rules--their slightly more complex syntax requires generalizing some
of the details of the acquisition routines.
It does not appear to be a difficult problem, however, and
beyond it lie some interesting issues. Given the success with acquisition
of object-level rules in the context of a bug, can the same be done with
meta-rules? What are the superficial manifestations of a bug that suggest
the need for a change in the way established knowledge is used (rather than
a change in the content of the knowledge itself)? We have considered this
briefly and the most obvious case seems to be one analogous to human
behavior. When someone inexperienced in a domain takes a plausible, but
(to the expert) inappropriate approach to a problem, the expert can often
spot it and inquire why the novice took that approach. Similar situations
may be encountered in which the program starts off on a plausible, but
incorrect track; the appropriate remedy may be a new meta-rule. This
appears to be one interesting direction for future work.
.SSS(|Limitations of the current implementation, future work|,STRATFUTWORK:);
There are several shortcomings in the present implementation. Some
are due to fundamental issues of system organization, while others are the
result of limited experience with these constructs and, thus, may change in
time.
One limitation arises from the way meta-rules augment the
performance program's control structure. In the present implementation,
their effect is constrained to the reordering or pruning of rule lists.
While this is useful, examples above demonstrate that it offers a limited
capability for encoding aspects of the control structure. More important,
it provides no means of effecting the more interesting capability of
switching methodologies. Since medical diagnosis is known to be a complex
set of behaviors (see, e.g., [[Miller75]), it might prove useful to be able
to shift back and forth between, say, a goal-directed and a data-directed
invocation of rules as the consultation progresses. (See {YON2 STRATFUTWORK}
for some thoughts on how this might be accomplished.)
A second limitation is the restriction on circumstances under
which meta-rules are invoked. As illustrated, they are invoked when a goal
is sought or when a conclusion is made. There are many other events that could
quite usefully trigger them. In particular, the %2failure%* of one of the
object-level rules might be very informative and could suggest a useful
reordering or pruning of the remainder of the list. The basic problem is
that meta-rules are simply not a general demon-like mechanism. This may
eventually be changed if a reasonably efficient scheme can be found which
will avoid some of the overhead typically associated with demons.
One particularly useful application of such a scheme would be its
use in conjunction with non-exhaustive application of the object-level
rules. We noted above that, due to the exhaustive search currently used by the
performance program, meta-rules typically do not change the final result
reached by the program but can, instead, make the program appear more
rational as it works to determine the answer. Non-exhaustive search might
be implemented by adding "after-the-fact" meta-rules to the system: These
would be meta-rules executed after an attempt had been made to determine the
value of a specific attribute. In this case meta-rules executed before the
search might indicate that only one or two reasoning paths should be tried.
Meta-rules executed after the search could test the strength of the
conclusions made so far and could perhaps indicate that the system should "go
back and try again," this time exploring additional paths. This would
permit
the creation of strategies that decide when the result is "good enough" to
make further search unprofitable and may prove quite useful when the rule
base becomes very large.
The present implementation of meta-rules also has a problem of
comprehensibility:# The translations of the meta-rules shown earlier are not
particularly lucid. This is due primarily to the primitive approach to
natural language used in the system, especially the clause-by-clause
approach to translation of rules. As the meta-rules begin to play a larger
part in controlling the system's behavior, it will become important to
provide a more sophisticated translation, one which yields more comprehensible
results.
There are also limitations that arise out of the decision to
encode strategies in the same production rule format as the object-level
rules. While this offers the important advantage of a uniform encoding of
knowledge, production rules are not well suited to the expression of
complex control structures. In particular, they are not a particularly
transparent medium for expressing a "chunk" of behavior that requires more
than a single rule (see [[Davis77a] for a discussion of this point).
More generally, the issue of an appropriate strategy language is still an
open question.
Problems also arise from the restricted syntax available in
{SYSTM MYCIN} and adopted, for the sake of uniformity, in &&. In particular,
the fact that the only "action" currently available is to make a
conclusion means that meta-rules can be used to perform only a limited
"direction" of the use of object-level rules, reordering or pruning the
list before it is invoked.
Finally, there is the subtlety of the distinction in the
implementation of the "statement-of-utility" and "line-of-reasoning" types
of strategy. As indicated earlier, at each goal the system retrieves all
the meta-rules for the current attribute, as well as for any attributes
above it in the current goal chain. It is necessary to distinguish between
rules that are intended to be applicable at only a single level (i.e.,
"statement of utility" types) and those that apply to an arbitrary
number of levels (i.e., anywhere along the line of reasoning leading to the
goal). This is handled currently by a somewhat obscure solution to what is
really a much larger, nontrivial issue:# the problem of implicit context,
described in {YON1 PRODRULES}. The difference in effect of associating
a meta-rule with an attribute as opposed to an object is another aspect of
this same issue and suffers from a similar obscurity.
.SKIP TO LINE 1;SS(Broader implications,STRATBROADI:);
The discussion thus far has centered around the concept of
saturation and our method for dealing with it, namely, the use of
meta-level knowledge as a site for embedding strategies to guide the
program. As previous examples have shown, this technique is also useful
for guiding program performance even when the system is not saturated.
At this point the discussion broadens to consider some interesting
additional issues that arise from examining the mechanisms used to
implement meta-rules. We consider in particular the implications that
follow from two features:# (a)##meta-rules' ability to select object-level rules by
direct examination of object-level rule code and (b)##meta-rules' use of an
explicit functional specification of retrieval criteria. The focus here is
on these techniques as they apply to programming in general, not just the
encoding of strategy information. We begin by examining in some detail the
difference between various approaches to referencing knowledge sources.
.SSS(Reference by name vs. reference by description);
Since strategies (in any form) are used to direct the invocation of
object-level KSs, they must have some way of referencing them. Two
fundamentally different approaches have typically been employed; we term
them %2reference by name%* and %2reference by description%*. The former
lists all KSs explicitly, while the latter offers a predicate indicating
required characteristics. The %ATHUSE%* construct of {PRLANG PLANNER} uses
reference by name, allowing the programmer to name one or more theorems
that are likely to be especially useful. The effect of a statement like
.STARTCENTERIT(A);
(THGOAL (WIN POKER HAND) (THUSE BLUFF DRAW3 CHEAT))
.ENDCENTERIT;
is to specify the order in which some of the plausibly useful theorems will
be applied. The %AGOALCLASS%* statement in {PRLANG QA4} is quite similar.
Meta-rules, on the other hand, effect reference by description. As
previous examples have illustrated, they make conclusions about a class of rules
that is specified by describing relevant characteristics. %AMETARULE002%*,
for instance, refers to %2rules which mention pseudomonas in their
conclusion%*. {PRLANG PLANNER}'s theorem base filter (%ATHTBF%*) construct is
another example of this general sort of capability:# It allows the
specification of an arbitrary predicate to filter the selection of theorems
to be applied to a goal.
There are numerous advantages to reference by description,
primarily in terms of the ability of the knowledge base to accommodate
changes. These are explored later in {YON3 STRATFLEX}. Here we
examine a more detailed point:# the implications involved in
two different ways of accomplishing reference by description.
.SSS(External descriptors vs. content reference); <<rearr starts here>>
One way to accomplish reference by description is via a set of
external descriptors. That is, a number of different characteristics could
be chosen and each KS described in terms of them. For an ordinary
procedure, for instance, the descriptor set might include elements
describing the procedure's main effect, any side effects, preconditions for
its use, etc. Strategies would then describe the relevant class of
procedures in these terms.
The second implementation is by direct examination of KS content
and is illustrated by meta-rules. For instance, when %AMETARULE002%*
refers to %2rules that mention pseudomonas in their premise%*, the relevant
set is determined by retrieving the premise of each of the rules in
question and examining it directly to see if it contains the desired
item.∪∪ This is accomplished via the template mechanism described in
chapter 2.∪ That is, the meta-rules examine the code of the
object-level rules to detect or infer the presence of any relevant characteristic.
This general notion of allowing one part of the system to examine the
rules (code) executed by other parts is based on three main
ideas. First, there is the concept of the unity of code and data
structure, first suggested in the notion of a stored program computer and
later made convenient by the {PRLANG LISP} language. Second, the rules
must be stored in a comprehensible form. In this case that means
interpreted {PRLANG LISP} code, written in a stylized form; but in general
any relatively high-level language will do. Finally, the syntax and some
of the semantics of that high-level language must be represented within the
system, to be used as a guide in examining the code. In the current
example, the syntax is represented by the template for each predicate
function (allowing each function to describe its own calls) and the
stylized form of rules. Semantics are supplied in part by internal data
structures, which indicate, for example, that %ASAMEBUG%* is an attribute.
.SSS(Benefits of content reference as an invocation mechanism,STRATGENERALI:);
.beginind content-directed invocation
.ind reliability
.ind expressiveness
.ind generalized invocation criteria
.ind flexibility
There are a number of interesting implications that follow from
the use of content-reference as an invocation mechanism. The technique
makes possible a system in which invocation has a greater degree of
%2reliability%* and %*expressiveness%* (defined below), a system that makes it easier for a
user to define his own %2generalized invocation criteria%*, and a system
with a higher degree of %2flexibility%* in responding to changes. We
consider each of these in turn, then review the limitations of our approach
and the difficulties that remain before the
benefits noted can be fully realized.
.SSSS(Reliability and expressiveness);
Effecting reference by description through direct examination of
KS content can be seen as another step in the development of KS
invocation mechanisms. To clarify this, consider breaking down the invocation
process into two phases: determining the %2relevance%* and determining the
%2applicability%* of a KS. The first involves the retrieval of one or more
KSs that may plausibly be useful; the second concerns the actual
determination of applicability. In the {SYSTM STRIPS} system [[Fikes71],
for instance, relevance of an operator is determined by the contents of the
add list, while its applicability is indicated by its preconditions.
.ind handle of a KS
.ind body of a KS
The determination of relevance for a KS will be based on some link
to it, a %2handle%* by which it can be referenced and retrieved (e.g., in
{SYSTM STRIPS}, the add list).∪∪We distinguish between the %2handle%* and
%2body%* of a KS:# The body is the part actually executed [or interpreted],
while the handle is anything that is used as a way of accessing the body.
Thus, for a subroutine, the name is the handle and its code is the body;
while for a {PRLANG PLANNER} theorem, the pattern is the handle and the
theorem code is the body. As will become clear, the handle and the body are not
necessarily distinct.∪ We will be concerned here primarily with the
various types of handles which have been used and, in particular, with
their %2reliability%* and %2expressiveness%* (defined below).
{YONTABLE INVOCMECH} sums up the discussion that follows.
Consider, first, the types of handles that have been used. In a
historical perspective, the concept of a subroutine (procedure)
can be viewed as the
introduction of the notion of a distinct, nontrivial KS. The only handle on
it was its name, assigned by the programmer.
The first major departure from this came in {SYSTM GPS}
[[Newell72], and {SYSTM GPS}-like systems such as {SYSTM STRIPS}. In the
latter, as noted, the handle on each KS is provided by the contents of
its add list. Note that part of the %2definition%* of the KS
itself (the add list) provides the handle and the name of the KS has
become inconsequential.
Production rules are similar, since they are retrieved on the basis
of symbols appearing in either their left- or right-hand sides, symbols
which are part of the definition of the KS itself.
With the advent of {PRLANG PLANNER}-like languages
({PRLANG PLANNER}, {PRLANG QA4}, etc.), the important concepts of pattern-directed
and goal-directed invocation were firmly established as standard
programming language tools. These languages provided links to KSs via
patterns that were used to describe either the goal which the KS could
achieve (consequent theorems) or the event to which it was relevant
(antecedent and erasing theorems). Once again, the KS name is irrelevant.
Consider now the expressiveness and the reliability of the handles
provided by current programming techniques (see {YONFIG EVGRAF}) and the
impact of using each of them. We define %2expressiveness%* as the richness of
the language that can be used in a handle. One crude measure is:#
Does it make any difference to program performance if every
occurrence of a KS handle in the program text is uniformly replaced by some
arbitrary string? That is, is the handle merely a token or does its
structure convey information?
The %2reliability%* of a handle is determined by the nature of the
relationship between the handle and the KS body. A crude measure might be
seen in the effect of editing the KS:# If I retrieve a KS because it supposedly
has some property (e.g., it supposedly accomplishes a particular goal), then can
I change the KS in such a way as to remove that property, yet leave unchanged
the invocation pattern based on that feature?
For example, the %2name%* of a subroutine is purely a token and is devoid of
semantics (except of course in the programmer's mind). There is only one
way to express which subroutine you want (by naming it); hence this
technique has minimal expressiveness. Since there is no formal connection
between the name and contents, arbitrary changes can be made to the code
without affecting whether or not the subroutine is invoked. In this case, the handle has
minimal reliability. As a result, the programmer himself must know exactly
what each subroutine contains and select, by name, the proper one at the
proper point in his program.
With the advent of pattern-directed invocation, the subroutine
acquired a %2pattern%* which is used as the handle. There is a limited but
useful sort of expressiveness here, in a syntax that typically permits a
broad range of patterns. The structure of the pattern conveys
information and, hence, can not in general be replaced by an arbitrary
string without affecting program performance. Consider, however, the
reliability of the link. Note that it is the programmer who writes both the
body and the pattern for the KS, hence there is no guaranteed
correspondence. Arbitrary changes can be made to the body of a
{PRLANG PLANNER} theorem, for instance, without changing whether or not it is
invoked.
Goal-directed invocation was another step toward increased
expressiveness as the pattern acquired an interpretation, which added
further richness to the language. In {PRLANG PLANNER}, for instance, there
are three classes of patterns (goal, assertion event, and erasing event),
while {PRLANG QA4} offers an extensive set of categories in a general demon
mechanism. But the reliability remains the same (i.e., minimal). Indeed,
there is the potential for much deviousness in allowing the programmer to
cause the invocation of an arbitrary body of code based on a pattern which
may or may not describe what the theorem actually achieves:∪∪And herein lies a
seductive trap. The KS handle is no longer a token but conveys
information. When that information is advertised as a "purpose," it is easy
to start believing that every KS is sure to achieve its advertised
"purpose."# Consider the psychological difference between asking for "any KS
whose pattern matches the following" and asking for "any KS that achieves
the following goal."# Note that the computational mechanism for both is
identical and the difference (the interpretation of the pattern as a goal)
exists purely in the programmer's mind. The first asks the proper
question, in that it assumes nothing more than it can deliver; the latter
is fraught with easily misinterpreted connotations. It is easy to forget
that it is the programmer's responsibility to make sure each KS achieves its
advertised effect.∪
.BEGINQUOTE;TURN ON "→";
The subroutines are not referenced by their names. Instead they are called
because they accept arguments with a certain structure, and because %2the
programmer claimed%* that they will solve goals of a certain class.
→from the {PRLANG QA4} manual [[Rulifson72], (emphasis added)
.ENDQUOTE;
As the final step in this dimension we have the use of a set of
descriptors, the "external descriptor" approach described earlier. Note that
this is a generalization of goal-directed invocation, since the "purpose" of a
KS is only one description of it. Any number of other facts about it may prove
relevant and could, equally well, be supplied. A suitably large set of such
descriptors would make possible a useful language for referencing a KS. As
%2external%* descriptors, however, they have no formal relationship to the KS
body, and their reliability remains minimal--arbitrary changes to the body may
render those descriptions inaccurate, yet the invocation pattern of the KS would
remain unchanged.
The link in {SYSTM GPS} and {SYSTM STRIPS} is, as noted, based on part
of the definition of the KS itself (the add list) and thus has a stronger degree
of reliability. Consider that we cannot, for instance, changed the effect of
the operator (say by changing one of the terms of the add list) without also
seeing a change in its invocation pattern.∪∪Note that such a change in the add
list may make the operator semantically incorrect (i.e., it may no longer
describe a valid operator in the domain). Content-directed invocation does not
guarantee that the operator is semantically meaningful, only that it does in
fact have the property for which it is being retrieved.∪ However, all of the
retrieval mechanism is contained in the means-ends analysis that is embedded in
the system interpreter and the programmer has no control over which KS is
invoked. Thus, while the handle on the KS is reliable, the user has no means of
expressing his preferences for which should be retrieved. Production rules are
similar:# The link is reliable because it is based on the content of the KS
(the symbols appearing on the left or right hand side), but there is the same
sort of single, "hardwired" mechanism that effects the retrieval, leaving the
user no opportunity to express a preference.∪∪It is possible to force specified
interactions by anticipating the operation of the retrieval mechanism, but this
is often difficult for a large system and is, in any case, contrary to the
"spirit" of the formalism. See [[Davis77a], especially Section 5, for a
discussion of the issue.∪
Traditional invocation mechanisms thus offer varying degrees of
expressiveness and reliability. Is it possible to obtain both of these at
once? The current implementation of meta-rules uses a technique that takes
one step in this direction; we term it %2content-directed invocation%* to
suggest its place in the ongoing development of KS invocation
methods.∪∪There has been a parallel evolution in access to memory locations, from
absolute binary, to symbolic addressing in assemblers, to relocatable core
images, on up to content addressable memories (e.g., {PRLANG LEAP} [[Feldman72]).
Content-directed invocation can thus be seen as the procedural analogue
of content addressable memory.∪
It has a high degree of reliability because, like production rules and
{PRLANG GPS}-like systems, it references the KS code directly. Recall that by
"reliability" we mean that the KS retrieved will in fact achieve the desired
effect. That is, %AMETARULE002%*, for example ({yonfig METARULES}), will
retrieve an object-level rule not because of the rule name, the rule number, or
other external descriptor, but because examination of the code of that
object-level rule reveals that it does in fact conclude about
enterobacteriaceae. Content-directed invovcation cannot of course assure that
the object-level rule makes this conclusion with the appropriate
justification--it would be far more difficult for the system to determine that a
KS not only achieves a desired effect but does so based on reasoning (or
actions) appropriate to and justifiable in the domain. Thus whether the
object-level rule deduces enterobacteriaceae for valid medical reasons is a
different issue that would require a great deal more inference on the part of
the system. We claim to have taken only a first step (from external descriptors
to content-reference) but submit that it can be a useful advance, especially in
a knowledge base undergoing frequent revision.
Content-directed invocation is also expressive, since it offers a way of
using any computable predicate (e.g., %AMENTIONS%* in {yonfig metarules}). The
link thus inherits its expressiveness from the programming language in which the
system is written.
To see the potential impact of this, consider once again the historical
perspective. The programmer using procedures effectively says "give me that KS
next," indicating it by name. In {SYSTM GPS-STRIPS} and traditional production
systems, the user has little or no control over which KS is invoked next.
{PRLANG PLANNER} made it possible to say "give me any KS whose pattern matches
this one"; in using that pattern as a designator of a goal, the request becomes
"give me any KS that (supposedly) achieves the goal designated." Finally,
content-directed invocation makes it possible to say "give me any KS that fits
the following description."# By writing the proper sort of description, we can
have invocation that is goal-directed, side-effect-directed, speed-directed--in
short, directed by any one or a combination of factors. Because direct reference
is made to the content of the KSs being retrieved, we have a high degree of
reliability as well.
Consider pursuing this one step further. The second clause of the
premise of the meta-rule in {YONFIG METARULES}
.STARTCENTERIT(A);
(THEREARE OBJRULES(MENTIONS CNTXT PREMISE SAMEBUG) SET1))
.ENDCENTERIT;
is one very simple example of content-directed invocation. It determines
whether or not an object-level rule mentions the attribute %ASAMEBUG%*.
Consider then the impact of second order meta-rules--they can be used to
select the criteria by which the KSs will be characterized. Thus we
not only allow the user to specify arbitrary criteria to control retrieval, but
make it possible for him to encode knowledge that decides dynamically
which are the most appropriate criteria to use.
Note that a plausible alternative to content-directed invocation would be the
formalization of the link between the external descriptors and the body of the KS.
There are at least two ways this mapping might be provided. The first is a
"descriptor verifier" approach. This would involve submitting to a deductive system
both the code for a KS and some descriptors for it, then allowing the deductive
system to attempt to prove the correctness of the descriptors (much like current work
in program verification). Another scheme would be to use a "descriptor generator,"
which, provided with the KS code and a characterization of the descriptors desired,
would automatically generate them. A simple version of this was done some time ago:
GPS was capable of constructing its own table of connections when supplied with
operators in the form of rewrite rules (e.g., symbolic logic transformation rules)
and a set of routines for defining differences ([[Newell59], [[Newell61]). It
matched the left- and right-hand sides of the rules and applied each difference
detector to the result. This was feasible because the KS "code" had a very simple
form, and because the "characterization of descriptors" was a procedure for finding
the relevant features.
More powerful versions of either of these, however, would require substantial
advances in the state of the art. It seems more reasonable for the time being to use
content-directed invocation, which employs a procedural definition of the
characteristic desired and allows the procedure to access the KS code, as the
function %AMENTIONS%* does.
.FULLPAGEFIG; <<KS INVOCATION MECHANISM TABLE>>
.TABLE(KS Invocation Mechanisms,invocmech:);
.BOXFIG
∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
KS Type } Type of Handle } Reliability } Expressiveness
∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
} } }
Subroutine } Name } Minimal } Minimal
} } }
GPS - STRIPS } Add list } Strong } Very limited,
} } } hardwired
} } }
} } }
Production } Symbols in } Strong } Very limited,
rule } rule } } hardwired
} } }
} } }
PLANNER } Pattern + } Minimal } 3 categories (goal,
theorem } recommendation } } assertion, erasing)
} list advice } } and limited syntax
} } }
} } }
QA4 } Pattern + } Minimal } Syntax similar to
operator } GOALCLASS } } PLANNER, but wider
} advice } } set of categories
} } } in a general demon
} } } mechanism
} } }
} } }
Content- } Arbitrary } Explicit, } Extensive,
directed } predicate on } formalized,} extensible,
invocation } KS contents } testable } softwired
∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
.ENDFIG;
.FULLPAGEFIG; APART; <<EXPRESSIVENESS-RELIABILITY graph>>
.GROUP SKIP 5;
.BOXFIG;
↑
} Content-directed
} invocation
} Set of external
} descriptors
}
E }
X }
P } Goal-directed
R } invocation
E }
S }
S }
I } Pattern-directed
V } invocation
E }
N }
E }
S } Subroutine GPS, STRIPS
S } production rules
}
α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂→
RELIABILITY
.FIG(Expressiveness and Reliability of KS Invocation Mechanisms,EVGRAF:);
.ENDFIG;
.SKIP TO LINE 1; SSSS(Generalized invocation criteria,STRATGIC:);
All of the development thus far has been in the context of "tuning"
a single control structure, in this case, goal-directed invocation. We
noted above that the expressiveness of content-directed invocation made possible
tuning based on a very wide range of criteria:# any criterion that could be
expressed in a computable predicate that examined the KS code. This is one
interesting ability that arises from the use in meta-rules of an explicit,
functional specification of desired KSs. That is, the meta-rule premise is, in
effect, an executable procedure for selecting the appropriate KSs.
The ability to specify retrieval criteria can be turned to another
use, which we term %2generalized invocation criteria%*. The point is
simply to apply this criteria-defining capability to the specification of the
basic control regime, rather than limiting its use to tuning an established control
structure. To see how this might work, consider that, for example, goal-directed
invocation might be specified as
.STARTCENTERIT(A);
Use rules that mention the current goal in their action
.ENDCENTERIT;
while data-directed invocation might be phrased as
.STARTCENTERIT(A)
Use rules that mention the current conclusion in their premise.
.ENDCENTERIT;
We might similarly specify new kinds of control regimes, as, for
instance, the "speed-directed" retrieval criterion mentioned above. While
accomplishing such sophisticated retrieval in its most precise and general form would be
very difficult (since it would require automating part of analysis of
algorithms), such a general solution is not required. Within the context of
{systm MYCIN}, for example, the speed of a rule is dependent on a small
number of well-known factors (including the number of premise clauses,
number of new [unexamined] attributes mentioned, etc.). Similar analyses
of other representations may yield analogous formulations, and even a good
approximation would still be very effective in guiding KS retrieval. Hence
as long as we are willing to work with a given representation (or set of
representations), we need not solve the problem in complete generality in order
to make use of the idea of generalized invocation criteria.
The ability to specify such generalized criteria appears to offer at least
three advantages. First, it frees the programmer from the limitation of using only
those control regimes (e.g., goal-directed or data-directed) already hardwired into
the programming language in use. That is, we have offered the programmer the notion
of retrieval itself:# The criteria for KS retrieval are no longer predefined and
embedded in the language interpreter, but can be specified and changed (even
dynamically) by the user himself.
Second, it makes possible an added degree of explicitness in program
representation. To see the benefits that accrue from such explicitness, consider
what typically happens when the available set of invocation mechanisms is incomplete
for a particular problem:## The programmer often resorts to various devious implicit
or indirect techniques to achieve the desired effect. One popular approach is that
of getting a multitude of effects from a single mechanism. Where KSs are retrieved
via pre-computed index lists, for instance, a common approach is to hand-tool the
ordering of these lists to achieve effects not otherwise available in the existing
formalism. For example, where goal-directed invocation is accomplished by using
pre-computed lists of operators, hand-tooling these lists can add a range of other
control regimes. In [[Waldinger74], for instance, the %AGOALCLASS%* lists were
hand-ordered to insure that the fastest operators were invoked first; the analogous
lists in {SYSTM MYCIN} have, in the past, been hand-tooled to effect a number of
different partial orderings on the rules that are invoked.
A similar example arises when using a multiple priority level
agenda of the sort described in [[Bobrow77]. Suppose, for example, we
wanted to insure a particular partial ordering of processes to be put on
the agenda. Note that there is no way to say explicitly, %2make sure that
these processes (in set A) are executed before those (in set B)%*.
Instead, we have to be indirect, and could, for instance, assign a priority
of 6 to the rules in set A and a priority of 5 to those in B.
There are a number of problems associated with trying to do these
sorts of indirect encodings, all of which seem to arise from the fact that
information is unavoidably lost by the indirection involved. Note that in
all the cases above, the intent of the hand-tooling and indirect priority
setting is nowhere recorded.
The resulting system is both opaque and
prone to bugs. To see the opacity of the system, consider,
for instance, the agenda example where, after the priorities
have been set, it will not be apparent %2why%* the processes in A were
given higher priority than those in B. Were they more likely to be useful
or was it desirable that those in A precede those in B no matter how useful
each might be?# After a while, even the programmer who set these
priorities may forget what motivated the particular priorities chosen.
Bugs can arise in this setting due both to execution-time events
and events in the long-term development of the program. Consider for
instance what happens if, during a run, before any of the processes in A
are invoked,
an event occurs which makes it clear that the
priority of processes in A
ought to be reduced (for reasons unrelated to the desired partial
ordering). If we adjust only the priority of those in A, an execution-time
bug arises, since the desired relative ordering may be lost. Yet there is
no record of the necessary interconnection of priorities to remind us to
adjust all of them. A similar problem can arise during the
long-term development of the program if we attempt to introduce another
indirect effect by juggling priorities and end up modifying those in set A
without making the necessary adjustments to those in B.
The problem with this approach is that it tries to use a single invocation
mechanism to accomplish a number of effects. It does this by reducing a
number of different, incommensurate factors to a single number, %2with no
record of how that number was reached%*. Meta-rules, on the other hand,
offer a mechanism
for making these sorts of considerations explicit and for leaving a record
of why a set of processes was queued in a particular order.
Third, meta-rules offer the advantage of %2localizing%* all of the
control information. Note that juggling priorities means trying to achieve
a global effect via a number of scattered local adjustments. This is often
quite difficult and can be very hard to change or update. Localizing each
such invocation criterion in a single meta-rule makes subsequent
modifications easier. Since all of the information is in one
place, changing a criterion can be accomplished by editing the relevant
meta-rule rather than searching through a program for all the places
in which priorities have been set to effect that criterion.
Our historical overview provides one further observation. Consider viewing
the progress from standard procedure-calling to techniques like goal-directed
invocation as making it possible to be less precise, and therefore less
restrictive, about the role of a given procedure in a program. Where invocation
by name (i.e., procedures) requires that we decide exactly %2where%* and
%2when%* the code is to be invoked, goal-directed invocation requires only that
we specify %2how%* a procedure is to be used. The perspective suggested here
moves us another step along that line, by considering retrieval separately from
the writing of a KS. The programmer can, if he desires, write a KS without
specifying how it is to be used and can leave this up to the invocation criteria
to decide.
The point here is not that the programmer should not specify such
information, since it can be very useful for cutting down combinatorics. For
inference rules, for instance, it is important to know which are more useful in
the goal-directed mode and which are more useful in the data-directed mode.
Such information can cut down search or control the number of forward
inferences drawn from a new assertion. The point is that if the programmer
does want to specify such things, it is better if he is not limited to making
that information synonymous with the handle used to retrieve the code. (This
occurred in {PRLANG PLANNER}, for instance, where the indication that a theorem
ought to be used in a goal-directed mode for a particular pattern became the
sole way of indexing it [by the single goal pattern].)# If we keep these two
things separate, we allow information about appropriate use to become a piece of
advice rather than a constraint.
.SSSS(Flexibility,STRATFLEX:);
.ind flexibility
The choice of a KS reference technique (name, external descriptor, or
content reference) can have a significant impact on the difficulty of making
changes to a program. As we will see, content reference offers a
number of advantages in this respect.
This consideration
becomes particularly important for the applications we have
described:# Since much of our effort has involved making it possible for
the expert to augment the knowledge base, we should take advantage of any
means of minimizing the difficulty involved in propagating the effects of a
change. Such flexibility will also become increasingly important as
knowledge base construction proceeds, since as a program gets larger it
becomes increasingly difficult to cope with the effects of changes.
For the sake of discussion, we identify two classes of such
flexibility:# %2Compile time flexibility%* is the ability to make
changes in the knowledge base between performance runs and then have those
changes integrated throughout the system; %2execution time flexibility%*
refers to the ability to switch strategies during execution, under program
control. This section deals with the former. Comments in
{YON2 STRATEXTIMEFLEX} below deal with the latter.
To judge the impact of selecting one or another of the reference
techniques, we examine two types of changes:# editing or adding a
(object-level) KS to the system, and editing or adding a strategy
(meta-rule).∪∪While the impact is illustrated in the context of meta-rules
and object-level rules, the point is more generally applicable to any kind
of KS in a system invoking any other KS, regardless of the level of
each.∪ See {YONTABLE STRATBENCH} for an overview.
Consider, for example, the
effect of editing (or adding) a KS and imagine that strategies used the
reference-by-name approach. First, after editing a KS in such a system, all
strategies that mention it must be retrieved and examined to see if they
still apply, and then must be edited accordingly. Next, since
it is also possible that the
revised KS should now be mentioned in other strategies, the rest of the strategies
must also be examined. Using the external-descriptor approach, we need
only update the appropriate descriptors, which would be stored with the KS.
In addition, the updating required should be evident from the sort of
editing done on the KS itself. All relevant strategies will then
automatically adjust to these changes. With content reference there is no
additional effort of even updating descriptors since the strategies will
adjust to the changes found in the edited KS.
Adding a new strategy to the system (or revising an old one) also
causes problems for the reference-by-name approach: It is necessary to review
all the KSs to determine which the new or revised strategy should
mention.∪∪There is a plausible objection to this:# It may be claimed that a
new strategy is often written with some specific circumstance and purpose
in mind and that this clearly restricts the number of KSs that need be
considered to a small subset of the total. This is entirely correct. And
it is on just such grounds that we would start to build the set of
descriptors to be used in the reference by description approach. In part,
then, the technique is simply a step toward greater formalization of
knowledge already used in informal and ad hoc ways.∪# Using external
descriptors, it is possible that no additional effort is required, if the
description in the new strategy uses the available "vocabulary" of
descriptors. If, however, it requires a descriptor not yet in
that vocabulary, we have the formidable task of reviewing all existing KSs
and adding to each the appropriate entry for the new descriptor.
Thus there is a fundamental shortcoming in the external descriptor
approach because it uses a fixed number of descriptive terms. Since adding
a new term to this set can involve a lot of work, it becomes a task that should
not be undertaken very often. Avoiding this updating problem is one important
advantage of content reference:# It gives meta-rules the ability to "go
in and look" for any characteristic deemed significant. As a result, the
addition of a new strategy with a new meta-level conceptual primitive is a
transparent operation.
To make this clear, consider the following simple example. The
performance program's backward chaining of rules produces a depth-first
search of an and/or goal tree, where each clause of a rule may possibly
sprout a new sub-tree. It might be useful, then, to try rules with the
fewest clauses first. This approach would require a strategy that said
something
like %2try those rules with three or fewer premise clauses first%*, and
might require a new meta-level primitive. In the external
descriptor case, a property indicating the relevant information would have
to be added to every rule.∪∪This may not be a very difficult task if it is
possible to write a bit of code that computes the relevant information and
then apply it to every rule. This is, in fact, what we are suggesting, with two
small but important differences. First, we don't bother to compute all
properties of all object rules, so a considerable amount of space may be
saved. Second, if this bit of code is kept around in a meta-rule, the
addition of a new object-level rule later on is much easier.∪ Content
reference makes the task much easier:# We can write a new function that
counts the number of premise clauses found in an object-level rule and use
the function in a meta-rule. Nothing at all need be done to any
object-level rule.
We claim, in addition, that the set of useful meta-level primitives
is potentially large and therefore difficult to define a priori. Thus,
over the course of most program development periods, it is effectively an
open set, to which new members are continually being added. It is thus
important to make this task as easy as possible. Where the external
descriptor approach requires analyzing each new KS with reference to each
of the descriptors, content reference requires simply that the new KS be
"added
to the pot."## It will subsequently be referenced by any strategy that
describes it appropriately.
To summarize, consider the difference between the first and third
rows of {YONTABLE STRATBENCH}. Note in particular how much easier it is to
accomplish a number of standard knowledge base modifications. This can
offer a substantive advantage when the knowledge base becomes
appreciably large.
.endind content-directed invocation
.FULLPAGEFIG; << flexibility benchmarks>>
.TABLE(Flexibility Benchmarks,STRATBENCH:);
.BOXFIG;
∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
REFERENCE } Edit or add } Edit or add
TECHNIQUE } object-level KS } strategy
∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
} }
} Check all } Check all KSs
Reference by } strategies to } to see which it
name } see which should } should name
} name it }
} }
} }
Reference by } } Possibly no
description } Update its } additional effort,
via external } descriptors } possibly have to add
descriptors } } new descriptor
} }
} }
Reference by } }
description } No additional } No additional effort
via content } effort }
reference } }
∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
.ENDFIG;
.SKIP TO LINE 1;SSS(Limitations);
The previous sections noted a number of the implications of using
content-directed invocation:## increased reliability and expressiveness of the
handle used to retrieve a KS, the ability to specify generalized invocation
criteria, and the flexibility of the system in responding to changes. There
are, of course, a number of substantive difficulties in realizing all these
benefits and a number of limitations to the techniques we have suggested. These
are reviewed here to help outline the range of applicability of the work.
.SSSS(Reliability);
The reliability of the "handle" provided by content reference arises from
the ability to examine the code of a KS, yet we have dealt somewhat
blithely in previous sections with this difficult problem. There are at least
two sources of difficulty. First, even for a programmer, reading and
understanding an arbitrary chunk of code can be difficult. Second, even if we
could read it, it is not always clear what to look for: Try to specify for
instance how to detect by reading its code what goal a procedure achieves.
&& currently has only the simplest form of code-examining ability,
made possible by several useful shortcuts. We rely first on the nature of
the representation in use. The organization of information in rules makes
it possible to say that, for example, "%2rules which mention %AIDENT%*ity in
their conclusion%1" is an example of goal-directed retrieval. Second, the
rules are viewed as a task-specific high-level language:# The primitive
terms they use are both domain-specific and reasonably abstract (e.g., "%2the
culture was obtained from a %ASTERILE SOURCE%1"). This
makes their code much easier to
decipher than, say, an assembly code version of the same thing. Finally,
the code is strongly stylized (the predicates and associative triples),
allowing us to use the template associated with each predicate function as
a guide to deciphering code. As noted in chapter 2, the template describes
the format of a call to the function (the order and generic type of its
arguments), much like a simplified procedure declaration. Each predicate
function thus carries a description of its own calls, and by referring to
that description (i.e., retrieving the template associated with the %ACAR%*
of a {PRLANG LISP} form), we can dissect the call into its components (see
{YON2 BKGNDRHLL}).
We have, of course, thus far used this ability in only the most
basic, syntactic ways. We have not yet developed means for deriving more
interesting semantic content by examining code, and this is clearly a
difficult problem. While the shortcuts described can be used with
representations other than rules, they are not universally applicable. But
while this whole problem is difficult, it is also a separable issue. That
is, the extent of the current capability to examine code is extremely
elementary, but even the simplest form of it makes available the
interesting capabilities displayed above.
A more subtle point arises out of the possible suggestion that the
scheme proposed here appears to be susceptible to the same criticism made
of {PRLANG PLANNER}:# In our case, the user writes both the KS code and the
predicates that examine it. There would seem to be room for chicanery in
writing predicates specially tailored to the body of a particular KS. It
is possible, for instance, to write a predicate that tests for the
appearance of a uniquely named local variable in a program body, or that perhaps
checks the time of day or phase of the moon.
Our claim, however, was not that the invocation criteria would
always be meaningful, but only that they would be made explicit and precise.
Thus, while it is curious to ask for a KS that contains the variable
%AZZ$XX%*, the user can in fact do this. The criterion may appear bizarre
and may in fact be achieving some other effect indirectly via that variable
name. But note that the criterion must be encoded explicitly in the predicate defined
by the user, and hence there will at least be an explicit specification of the
criterion used. This is an improvement over the situation where a list is
hand-ordered, with no record left behind. We have supplied a means of
specifying invocation criteria and a technique that can, if used correctly,
insure that KSs are accurately described (i.e., by referencing the code
directly). There are no constraints on how the user may choose to apply
that capability, but any deviousness will at least be more explicit.
A further objection to our approach might claim that allowing
arbitrary predicates to examine and characterize a KS may result in odd or
unanticipated characterizations. This may in fact be an advantage and
raises an interesting point. The use of knowledge in odd or unexpected
ways is one aspect of that elusive quality, creativity. With this scheme,
we have taken one
small step toward making it possible for the system to
discover that a particular KS has a characteristic that may not have
occurred to the programmer who wrote the KS code. As a result, the system
may find unexpected applications for its knowledge.
Even with the best of intentions, however, there remains the
question of the correctness of the code that implements the content
examination. That is, what the programmer intends to say in this
invocation criteria "language" and what he actually writes may be slightly
different. Have we, then, only pushed the problem back one level? No,
because it has been formalized as well. Note that the "language" supplies
a precise and explicit expression of the invocation criteria. Correctness
is at least a well-specified and testable question.
.SSSS(Expressiveness and generalized invocation criteria);
One of the weaker claims made above concerned the expressiveness of
content-directed invocation (and, by extension, the expressiveness of
generalized invocation criteria). The weakness lies in our suggesting that
the programmer use the programming language itself to express retrieval
criteria, without having supplied any guidance or hints about how to do this
effectively.
The combination of the meta-rules and {PRLANG LISP} is, at best,
adequate (in the sense of being able to express any computable predicate)
and extensible only because, for example, new predicate functions can be
added to the rule language by writing them in {PRLANG LISP}. It would be
better, of course, if the meta-rule language already included a set
of primitives that provided a foundation for expressing
invocation criteria. Then we could suggest not only that "it's useful to
be able to define your own, generalized invocation criteria" but might
also say, "and here's a well-designed language that will help get you
started, without restricting you since it's also extensible."## We
have not as yet developed such a language; this is a focus for continued work.
The problem is difficult for many reasons, including the fact that
the task of assembling the "vocabulary" of descriptors may appear quite
imposing, and perhaps endless. What guarantee have we that there are in
fact a finite number of descriptors (i.e., a finite number of conceptual
primitives for describing knowledge), rather than an infinite number of
special characteristics?## There may be no guarantee, but the benefits are
in any case incremental--it is useful to write any of the system strategies
in this form, so even a subset of the entire collection is useful.
.SSSS(Flexibility);
We have emphasized the benefits of flexibility, but it is important
to consider these benefits in the appropriate context. While it may be
obvious, it is worth noting that the task at hand must somehow require this
kind of flexibility. In our particular application it arises from the
emphasis on the necessity of incremental construction of large performance
programs. The central point is that there will be a large number of
knowledge sources and strategies, with frequent changes to both over an extended
period of time. In this case there is a premium on the ability to organize
and manipulate knowledge. This is not necessarily true for smaller,
well-established systems whose knowledge base has stabilized.
.SSSS(Speed);
All of the advantages claimed for content-directed invocation
depend on the indirection inherent in content reference. Yet examining KS code
to find some property can be a time-consuming affair, even when looking for
the presence of a particular token. The potential for loss of speed becomes
acute when we consider the time taken in inferring the presence of some
more subtle property, which requires invocation of several meta-rules for each
object-level rule.
However, like many similar constructs, most of the computational
cost can be paid in a background computation between performance runs.
During that time the system could compute the sets of KSs determined by the
various descriptions.{FOOTNOTEPREFACE}
.SEND FOOT ⊂ FOOTNOTESEND
There are nontrivial problems associated with the appearance of free
variables in the description parts, as in:#
.INDENT 0,0,0;
%2if conditions A and B hold, use any KS which deals with white cell
counts at least as high as that of the current patient.%*
.BREAK
It is still possible, however, to turn this into a list of specific KS names.
Consider the total range of the white cell count. Each KS in the
system which deals with it will be relevant to a specific value or range
of values. Thus, we can divide up the total range into, say, m different
segments, and in each segment a specified set of KSs will be relevant.
The single strategy above would have to be replaced with m strategies of the form,
.BREAK;
%2if conditions A and B hold, and the white cell count is in range%Ci%*
then use α{KS%Ci1%*, KS%Ci2%*,...α}
.CONTINUE;SELECT FNFONT;
where range%Ci%* is a segment of the total range and the descriptions have
been replaced with the sets of relevant KSs. The same technique works for any
continuous variable, of course; discrete valued variables are a degenerate case
in which all the KSs are relevant to one or more single values rather than a
range.
.⊃;
The results might either be saved for execution time use, or, in a form of
"pre-compiling," the source code might be rewritten, replacing the
descriptions with the sets they define. This offers both the flexibility of
.ind flexibility
reference by description and the speed of reference by name.
Other constructs (e.g., {PRLANG LISP} record structures) offer
similar advantages, in providing a level of insulation from the effects of
changes, without imposing execution time overhead. This particular
example, however, effects a very standard compiler-style transformation:
replacing a constant with its value. Since (by our definitions) the total
KS set is fixed at compile time, the descriptions in a strategy are really
constants and can be replaced by their values. This offers the symbolic
analogue of the ability to write (SQRT(PI)/7), with the compiler doing the
work to replace it with .253207683. The benefits of flexibility and
clarity are identical.
It may be useful, then, to picture this process as a generalization
of the usual view that there are two levels of code (source and machine
language) and work with multiple source codes, each with its own compiler.
This is indicated in {YONFIG LEVELSOFCODE}, with appropriate numbers to
indicate level.
.STARTFIG;
.BOXFIG;
α...source%Bii%*
==compiler%Bii%*==@
###source%Bi%*
==compiler%Bi%*==@
###source
==compiler==@
machine language
.FIG(Levels of code,LEVELSOFCODE:);
.ENDFIG;CONTINUE;
Each source further to the left is typically easier to read and understand,
and more flexible, but also slower. It seems plausible to suggest that many
of the techniques accepted for compilation and optimization of arithmetic
expressions may have analogues in symbolic computation as well. (Related
ideas are found in [[Low74] and [[Samet75].)
The generalized view of {YONFIG LEVELSOFCODE} also demonstrates
another point:# The distinction we have drawn between compile time and
execution time is one the user can determine on his own. The decision of
what level of code to execute is entirely open--the higher level
versions are more flexible, the lower level versions are faster. There is
currently no way to have both at once, but given good compilers, the
transformation is relatively painless.∪∪Work in this vein is described in
[[Mitchell70], which explores a programming language that makes possible
the execution of different levels of code in a manner that is transparent
to the user. See also [[Hansen74], which describes a compiler that
incrementally compiles and optimizes code according to the patterns of use
and modification of the code.∪
In general, then, the dividing line can be drawn at any point.
Whatever is relegated to being a compile time transformation can be done in
background mode and hence costs nothing at execution time.
.ind complexity
Note that this also has some impact on the issue of complexity. It
uses a succession of high-level languages, each of which
suppresses more implementation detail and concentrates instead on the more
important issue of knowledge organization and use.
.SSSS(Limitations:# Summary);
The point then is not that content-directed invocation ought to be
used exclusively, nor that it replace concepts like goals, patterns, etc.
We are concerned with the reliability of the connection between KS
handles and KS code, how expressive the handles are, and what they
contribute to the flexibility of the system in the face of changes to the
knowledge base. Where possible, then, the approach of
content-directed invocation provides a way of assuring a degree of
reliability, can offer a more expressive syntax, and provides a
flexibility that can be very useful.
.SSS(Future applications:# Choosing control regimes,STRATEXTIMEFLEX:);
We described the use of strategies as a means of "tuning" a
control structure and suggested in addition that content reference offered
a means of defining generalized invocation criteria. While it has not as
yet been implemented, we can imagine pushing this one step further. By
adding another layer of rules above the invocation criteria, we might gain
the ability to choose from among the set of criteria, that is, to choose the
control regime to use. There would be a number of rules defining
various retrieval criteria (goal, event, etc.) and a number of (meta-)rules
which selected from among these rules and hence chose a control structure.
This would make it possible for the program to
dynamically change control structures as a problem progressed (an ability
lacking in the current implementation, as noted in
{YON2 STRATFUTWORK}).
.ind flexibility
Such "execution time flexibility" would make possible a number of
interesting abilities. Consider, for example, a program
designed to do heuristic search. For domains in which a single search
procedure does not provide effective performance, it would prove very
useful for the program to be able to decide from moment to moment what form
of search would most likely be successful. It might thus use branch and
bound at one point, hill climbing at another, and so on. Note that we are
not speaking of a pre-programmed succession of techniques, but an ability
to choose each in response to changes in the problem state.
A more relevant example would be a system that attempted to
simulate the diagnostic behavior of an experienced clinician. Such behavior
has been found ([[Rubin75], [[Miller75]) to be a complex shifting back and
forth between processes of
collecting data (event-driven implication), establishing
causal chains (heuristic search), verifying (goal-directed search), and
others. This is reminiscent of the general perspective on knowledge
organization described earlier, since the physician is quite clearly
changing his entire approach under the control of strategies ("clinical
experience") that choose the most appropriate response.
Few computational systems have offered very much of this sort of
flexibility, however. Typically, this results from
three interrelated causes. The problem is that often an extensive amount of
knowledge is (a) embedded in the control structure, (b) represented there
only implicitly, and (c) treated on a special-case basis. In fact, much of
what is typically described as clever coding or implementation technique
often represents important insights into useful strategies. For example,
[[Green69], in describing modifications to resolution to allow his system to
deal with program construction, mentions in passing several interesting
domain-specific strategies. Expressing such chunks of knowledge as distinct
strategies has in the past been inhibited by the lack of a convenient
formalism and the difficulty of generalizing what may have been seen
initially as simply a special-case coding trick.
Yet the desire for increased flexibility has a long history. Much
of the early speculation about programs that could learn centered around
the ability to shift strategies dynamically as the situation required.
Gelernter mentioned it explicitly in 1959 [[Gelernter59]; ten years later
Green ([[Green69]) discussed somewhat more concrete proposals centered around the
possibility of expressing strategies in the same first-order predicate
calculus that the rest of his system used. Meta-rules of the sort
described in {YON3 STRATCSINFO} make possible a limited form of
execution time flexibility. They make part of the system's control
structure explicit and accessible, and hence manipulable by other
meta-rules.
What we are looking for, then, are "softwired" strategies. Achieving
this objective is predicated on overcoming the three problems mentioned, yet
this is often not difficult to do. First, the knowledge should be isolated as a
distinct chunk, rather than embedded in the system code (e.g., by putting it in
a single meta-rule). Second, the knowledge should be made explicit,
identifying exactly what it is that the system should know (e.g., the criteria
for deciding between control structures).
Finally, this well-defined chunk should be generalized as far as
possible, to provide maximal power. By "generalize," we mean that it should be
considered not as a special case or clever trick but, as far as possible, as a
fundamental principle of knowledge organization.
If all of this is really so useful, why isn't it common practice? The
primary reason is that new problem-solving methods are still being uncovered and
explored--their power, potential, and applicability are yet to be totally
defined. We are proposing a framework for integrating a number of methods,
based on the belief that there are now a sufficient number of techniques
understood well enough that we can begin examining the problem of integrating
many of them into a cohesive system.
But why consider the whole tool set, with all the associated cost? The
answer may lie in the nature of the problems currently being explored.
Chapter 1 noted the trend toward real world problems of significant size.
Where a single methodology may prove powerful enough to handle
well-isolated tasks in selected domains, the broader scope of real world
problems appears to require a correspondingly broader collection of
abilities. Strategic knowledge may provide a facility for directing their
use.
.ind flexibility
Thus, the primary advantage of increased execution time flexibility
is the potential for building more flexible programs. Systems equipped with a
single "hardwired" strategy, hence a single approach to the problem, would
appear to suffer the same shortcomings as the general problem solver type
programs. The latter proved unable to deal with difficult problems because of
their single, domain-independent methodology, which could not be modified by
important and useful domain-specific knowledge. Similarly, current
task-specific programs, with their domain-specific methods, cannot
dynamically shift the way they function and have an analogous limitation.
.SSS(Review);
The central aim of this section has been to consider the broader
implications that follow from the techniques used in implementing
meta-rules. The discussion focused on two techniques--content-directed
invocation and generalized invocation criteria--and considered their
implications as programming techniques in general, independent of the issue
of encoding strategy knowledge.
We began by examining different approaches to referring to KSs and
defined the idea of content reference. The use of this form of reference as
a basis for KS retrieval and invocation was termed content-directed
invocation and was compared to previous approaches to invocation.
This historical overview suggested that content-directed invocation offers
an added degree of reliability and expressiveness in invocation. The
technique also offers a way of making the criteria for KS retrieval
accessible and, hence, more easily modifiable, rather than predetermined and
hardwired into the language interpreter, as is the case for most
programming languages. Content-directed invocation was also seen to offer
.ind flexibility
a number of advantages in terms of the flexibility of the resulting system:# It
is easier to introduce changes into the knowledge base in systems using
this technique.
Generalized invocation criteria arose from making the invocation
criteria accessible and from specifying them explicitly and functionally.
This technique was seen to offer significant advantages in terms of
effecting control structures explicitly rather than via a range of indirect
effects.
Content-directed invocation and generalized invocation
criteria appear to be programming techniques that offer potential increases in both the
reliability and expressiveness of the invocation process, that offer increases
in the flexibility of the system in response to changes in the knowledge
base, and that permit explicit specification of invocation criteria.
We also examined several limitations of the current implementations
and explored difficulties that have to be overcome before the full
benefits of these techniques can be realized.
Finally, we speculated about the possible use of meta-rules in
creating a system capable of adaptively changing its control structure as
the problem solution proceeds.
.SKIP TO LINE 1; SS(|A Taxonomy, of sorts|,STRATAX:);
In this section the discussion broadens beyond the specific
implementation of strategies demonstrated by meta-rules. We
examine the kinds of strategies that have been used in a variety of
systems, with the aim of developing a rough taxonomy of strategy
types. This, in turn, will help provide a better understanding of the range
of possible strategy types and set in perspective the work on meta-rules.
The dimensions of the taxonomy are:
.BEGINLIST;
(a)\generality,
(b)\degree of explicitness,
(c)\organization, and
(d)\character.
.ENDLIST;
.continue
While the set is not necessarily comprehensive, these four appear to
capture a number of interesting distinctions and help characterize the
range of possibilities. Examples of actual systems are used to illustrate
sample points in each dimension.∪∪Note that many of the references cited
used a range of techniques so that at times only selected aspects of each
may be relevant.∪
.SSS(Generality);
The most general strategies are those we will term %2representation
independent%*, since they describe problem-solving approaches which can be used
no matter what underlying representation is chosen. As an example, the
general idea of a goal-directed ("working backward") vs. a data-directed
("working forward") approach is relevant over a wide range of problem
organizations and representations. Polya [[Polya54] describes several such
techniques; a recent book by Wickelgren [[Wickelgren74] deals with the
subject in more general terms. An interesting and very abstract approach is
taken in %2Strategy Notebook%* [[Interaction72], which explores six
categories of strategies and offers analyses of the strengths and
weaknesses of each. (The last category is labeled "metaheuristics" and
describes several very general second-order strategies.)
The work in [[Green69] is a good example of the use of
%2domain-independent%* techniques. That system used first-order predicate calculus
and resolution theorem proving. Strategies employed included unit
preference, set of support, a bound on the number of levels explored, and
the deletion of subsumed clauses. Since these techniques are meaningless
outside the context of theorem proving, they are not independent of the
representation. The domain independence of the underlying methodology,
however, indicates the applicability of the techniques to the
theorem-proving process in any domain.
A second example of domain independence
is the concept of planning in abstraction spaces,
as described in [[Sacerdoti73]. This system was based on the means-ends
analysis methodology of {SYSTM STRIPS} and used a powerful strategy of
planning at multiple levels of detail. Since the basic task in
{SYSTM STRIPS} is the choice of an operator whose application moves the system
closer to the goal, the use of repeated planning at successively lower
levels of detail becomes a way of directing the choice of operators and is
thus a domain-independent strategy.
By contrast, Gelernter's early work on a geometry theorem prover [[Gelernter59]
has some interesting examples of %2domain-specific %*strategies. It takes
a problem reduction approach, setting up an exhaustive list of possible
subgoals on the basis of available axioms and theorems. Subgoals are
ordered, however, on the basis of several domain-specific criteria:# For
example, goals involving vertical angles are chosen first because they
often turn out to have one-step proofs.
Finally, as illustrated earlier, meta-rules have been used to
express strategies that are %2goal specific%*. The %ATHUSE%* construct in
{PRLANG PLANNER} and the GOALCLASS statement of {PRLANG QA4} are
programming language constructs that offer the facility for writing similar
sorts of goal-specific strategies.
.SSS(Degree of explicitness);
A second dimension concerns the degree of explicitness
with which strategies are represented. %2Explicit%* strategies are those that
are embodied in their own distinct constructs and that can be identified as
separate entities in the system. %2Implicit strategies%* come in two varieties.
Those that are bound up in some other aspect of the system (typically the
control structure) we refer to as %2implementationally implicit%*. In this
case the essential idea of the strategy has been coded explicitly in the
system,
but that code is embedded (perhaps quite subtly) in other constructs.
%2Conceptually implicit%* strategies are those for which there is no
distinct encoding mechanism anywhere in the system. Typically, their effect is
realized via some side-effect of a process that other parts of the system are
tuned to detect. Since one of the global themes in this work concerns the
virtues of making all knowledge in a system explicit, we will make the case
below that the first of these three approaches is the most advantageous and
that the last presents problems.
The work reported in [[Howe73] is a good example of a conceptually
implicit strategy. That system used a production rule style representation of
chemical reactions to solve chemical synthesis problems. Certain reactions
(which were capable of supplying major structural features) were chosen as
sufficiently desirable that they were considered important to use, if at all
possible. This strategy was effected by leaving part of the precondition side
of these rules incompletely specified. That is, the "details" of the
preconditions were suppressed, a technique that can be seen as a special-case
implementation of Sacerdoti's levels of abstraction idea. The rules thus
appeared applicable in contexts that were, in fact, not exactly correct. The
remainder of the rule was tailored to check for these mismatches and attempted
to take care of all the necessary details before the rule was invoked. Since
the rules were hand-coded to provide for this suppression of detail, the
strategy is effected indirectly and has no explicit representation anywhere in
the system.
The work of [[Green69] and [[Sacerdoti73] are examples of implementationally
implicit strategies. In both, the strategies are realized as distinct sections
of code, but the code is embedded in the control structure. Green notes
that while there is a certain range of control available over strategy if
the user understands program parameters (e.g., the level bound on resolution), more
extensive changes require knowledge of {SYSTM LISP} and an ability to recode
parts of the system.
Finally, meta-rules are an example of explicit
representation of strategies, since they are constructs independent of the
control structure and represent strategies in much the same way that
object-level knowledge is represented by object-level rules.
.SSS(Knowledge organization,STRATORG:);
The next dimension concerns the organization of
strategic knowledge and considers
the indexing scheme around which the
strategies are organized. A number of different approaches have been used,
among them are strategies organized around:
.BEGINQUOTE;
%2KSs%*:##In {SYSTM HEARSAY II}, for instance, each KS carries with it a
description of the circumstances under which it is most relevant.
.SKIP 1;
%2Goals%*:##As illustrated, meta-rules are associated with specific goals.
.SKIP 1;
%2Goals in context%*:##Since {PRLANG PLANNER}'s "advice list" of likely
theorems
to try (supplied by the %ATHUSE%* and theorem base filter constructs) is part
of a specific goal statement, the advice can be organized by both goal and
context. That is, two %ATHGOAL%* statements may have the same goal pattern
but different advice lists because they are in two different theorems.
.SKIP 1;
%2Events%*:##The %AWHEN%* statement in {PRLANG QA4}, for example, offers a rich
syntax for describing events, along with associated specified responses. In
general, "event" can be interpreted broadly to refer to any configuration of the
data base allowing strategies to be organized around "situations" (data base
configurations) of varying levels of specificity.
.ENDQUOTE;
For the purposes of this discussion, it will be useful to make the
simple distinction between strategies that are organized around individual
KSs (the first example; they will be referred to as %2KS-centered%*) and
those that are organized around anything else (all the rest;
%2non-KS-centered%*). Note that those in the first class are %2indexed%* by KS
and %2refer%* to goals or events in which the KS is useful; the latter are
%2indexed%* around goals or events and %2refer%* to KSs.
.SSS(Character,STRATCHAR:);
The final dimension offers four classifications for describing the
"character" of strategy content. These four arise from two independent
distinctions ({YONFIG STRATCHARFIG}) that provide a framework for
understanding the different types of meta-rules explored earlier. They are
described initially
in the paradigm of tree search and then generalized to
demonstrate applicability for a range of problem-solving paradigms.
Specific examples illustrate each classification.
A modified breadth-first tree search might involve collecting all
the nodes that are descendents of the current node and attempting to
decide which is the best to pursue. Information concerning the utility of
each node might be of two forms. By %2individual utility%* we mean the sort
typically found in heuristic search evaluation functions. For our purposes,
its essential characteristic is that it gives a utility figure for a node
based solely on knowledge about that single node and about the current
state of the world. It does not refer to any of the other nodes.
A %2comparative utility%*, on the other hand, specifically refers
to more than a single node so that it can offer statements about their
relative utility.∪∪Note that while it is possible to arrive at such a
comparison by examining individual utilities, this refers to strategies
that compare two nodes explicitly.∪
Now take a depth-first view of the tree and imagine that the nodes
represent potential invocations of backward-chained rules. As we saw
earlier, a sequence of several of them a few levels deep can be viewed as a
"line of reasoning."# We can thus have strategies which
indicate either "this line of reasoning is useful" (individual utility) or
"this line of reasoning is more useful than that one" (comparative).
The primary advantage of the line-of-reasoning type strategy
is its ability to direct the system through local minima of evaluation
functions. Since one intuitive
aspect of intelligence is the ability to perform actions that may
superficially appear counterproductive (but which are in fact useful), this seems
to be an important source of knowledge.
By making a few simple replacements, this scheme can be generalized
to fit many forms of problem solving:# For "node", read KS; for "descendants
of the current node," read plausible knowledge source set; and, finally,
replace "depth" with time. Thus, instead of speaking of evaluating the
nodes at a given level of the tree, we speak of choosing a KS from the PKS
set; instead of thinking of search more than one level deep, we think ahead
to the invocation of more than one KS.
With these substitutions, we can also take another look at each
strategy type and consider examples from current systems. There are
meta-rules illustrating two of these categories: %AMETARULE001%* is of the
individual utility type, and %AMETARULE002%* indicates comparative utility.
There are numerous examples in other systems as well. The
preconditions of the operators in {SYSTM HEARSAY II} can be viewed as
individual utility statements, since they are associated with an individual
KS and describe the circumstances under which that KS is appropriate,
without referring to other KSs.
In [[Waldinger74] there are comparative
utility strategies embodied in the %AGOALCLASS%* statements which specify
an order for the use of applicable theorems. The {PRLANG PLANNER} example
above is another instance
of a comparative utility strategy; it makes explicit reference to more than one
KS in order to specify a relative ordering.
One early example of a line-of-reasoning type strategy is
mentioned in Samuel's discussion of his checker program [[Samuel67], where
.ind principle line
he terms it a "principle line."# The macro operators in {SYSTM STRIPS}
described in [[Fikes72] provide another example, as do meta-rules (although
we have not as yet uncovered any examples specific to the medical domain).
.STARTFIG;
.SKIP 2;
.BOXFIG;
Breadth Depth
⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
} }
Individual } Individual utility Line of reasoning }
} }
} }
Comparative } Comparative utility Comparison of lines }
} of reasoning }
} }
α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
.FIG(Strategy characteristics, STRATCHARFIG:);
.ENDFIG;
.FULLPAGEFIG;
.TABLE(The Strategy Taxonomy,STRATAXTABL:);
.BOXFIG;
∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
Dimension } Sample points } Example
∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
} }
Generality } }
} Representation independent } Polya
} Domain independent } Green, ABSTRIPS
} Domain specific } Gelernter
} Goal specific } PLANNER
} }
} }
Explicitness} }
} Conceptually implicit } Howe
} Implementationally implicit } Green, ABSTRIPS
} Explicit } TEIRESIAS
} }
} }
Organization} }
} KS-centered } HEARSAY II
} Non-KS-centered, } PLANNER: THUSE
} referral by name }
} Non-KS-centered, } PLANNER: THTBF,
} referral by description } TEIRESIAS
} }
} }
Character } }
} Individual, breadth } HEARSAY II
} Comparative, breadth } PLANNER, QA4
} Individual, depth } STRIPS macro ops
} Comparative, depth } - - - - -
} }
∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
.ENDFIG;
.skip to line 1;
.SS(Limitations of the general formalism,STRATLIMIT:);
There are several fundamental problems associated with
a fully general implementation of the meta-rule framework:# First, it is not
always possible to organize a program as a collection of discrete knowledge
sources; second, there is a considerable intellectual effort required to
assemble all the elements necessary for the general implementation; third, the
scheme will not work well if rules are created dynamically (i.e., during a
performance run); and finally, not all of the overhead required for execution
time flexibility can be restricted to the background and may impose a
significant reduction in speed.
.SSS(Program organization);
The need to organize the program as a collection of discrete KSs is
perhaps the most fundamental limitation encountered. While it may be
possible to construe the definition broadly enough to fit almost any
program, it is not always an informative view. There seem to be two
important factors in deciding whether, and how, to decompose a program into
distinct KSs:# (a)##The proposed KSs should be self-contained, in that each
can by itself make some contribution to the problem solution, and (b)##the
problem should be sufficiently ill-specified (in the sense discussed in
{YON2 STRATISP}) that there is no predetermined sequence of KS invocations
that will solve the problem; instead there is, at each point, some
indeterminacy about which KS to invoke.
If there is but a single KS in the program or (what amounts to the
same thing) if the various sources of knowledge are so intertwined that
separating them is impossible, then we clearly can't meet condition (a).
Similarly, if there is an algorithmic solution to the problem, then we have
none of the indeterminacy suggested in (b) and don't need all the
machinery outlined above.
.SSS(Intellectual difficulty);
The intellectual difficulty of implementing this approach arises
out of several factors. It is not often easy, for example, to describe
rather than name a KS. Consider the segment of code in {YON1 STRATBROADI}
that might appear in a {PRLANG PLANNER} version of a poker game. The
strategy there is to try bluffing, if that doesn't work draw three cards,
and if all else fails, cheat. To replace that with a description-oriented
approach requires a more basic understanding of the domain and of the
strategy being expressed. A rewritten version might say something like
"first use any psychological ploys to discourage the competition, then try
something that will improve your hand, and finally do anything that will
make sure you win."# Each of these is a more general description of the
entire class of theorems from which each of the ones named might have been
drawn. This is not often easy to produce and makes certain assumptions
about the nature of the application domain. In particular, the domain must
be sufficiently formalized (or formalizable) that it is a reasonable task
to look for meta-level primitives. There are clearly domains for which
this is not true.
Despite these difficulties, the direct benefits are considerable.
.ind flexibility
The resulting flexibility can be an important tool in the construction of a
very large system. There are, as well, indirect benefits. We have noted that
this approach requires a more basic understanding of the domain and
strategy. This in itself can be beneficial and lead to further insights.
More important, however, the resulting strategy offers a more complete
statement of the relevant knowledge. It makes more evident what it is
the strategy expresses and why the system performs as it does. It is thus
another example of one of our recurring themes--the benefits of the explicit
representation of knowledge.
.SSS(Dynamic rule creation);
The compile-time vs. execution-time distinction and the "pre-compilation"
of descriptions into corresponding sets of rule names offer efficiency only if
the addition of rules to the system is restricted to the time between
performance runs. The approach we have been describing imposes a significant
cost on the attempt to add rules to the knowledge base while the program is in
the midst of a performance run. At worst, it means all descriptions in
strategies have to be run "interpreted," constantly recomputing the applicable
set of rules. A slightly more efficient solution might employ an incremental
compilation, which recomputed all the strategy descriptions with reference to
the single new rule. Which of these is more desirable depends on the individual
system, but in either case the computational cost is significant.
.SSS(Overhead);
The final problem is the cost in speed of great execution time
flexibility. If, at every point where a KS must be chosen, the system
performs a full-blown re-analysis--one that includes deciding once again on
a methodology, deciding how to decide, and so on--nothing would ever get
accomplished. Such continual complete reappraisal is in most cases a
waste of time and should not be done. The question is, thus, how to invoke
all (or any) of this "deciding-how-to-decide" procedure only when
necessary. There are several possibilities.
The first, and perhaps the most effective, technique becomes clear
if we recall our definition of ill structured problems. If a problem is
completely ill structured, then the use of the fully general machinery is
warranted. To the extent that it is well structured, the machinery is
inappropriate. The point then is to combine both of these and to allow each
to help answer the fundamental question of which KS to invoke next. The
answer may then come from either the fully general "deciding-how-to-decide"
mechanism or from one of the structures that expresses the known connections
between KSs.
The result may be pictured as a construction in which the fully
general re-analysis mechanisms play the role of mortar, occasionally
holding together bricks (structured subproblems), at other times filling in
molds (the super-structure). The size of the molds and bricks may vary
widely, corresponding to the extent of understanding of different aspects
of the problem. The issue thus becomes where and how the problem is cut up.
As much of it as possible should be embodied in structures that reflect
known interrelationships, leaving the most general technique as a mechanism
available either to direct the use of those structures or to fill in if none are available.
To make this abstract picture more concrete, consider the place of
the meta-rules in {SYSTM MYCIN}'s problem-solving formalism. The major
superstructure there is the backward chaining of individual production
rules producing an and/or goal tree. Within this framework, meta-rules are
used to help guide the search through the tree. This arrangement
constrains the general (and expensive) decision mechanism to a collection
of well-specified locations. It can thus prove useful even when applied in
only a part of the overall system.
At the beginning of this chapter we claimed that the framework of
knowledge organization suggested by a fairly general conception of
strategies offered a useful and illuminating device for knowledge explication.
This point can be illustrated by this same issue of problem structure. It was
noted, above, that the unrestricted use of the most general formalism is in
most cases a waste of time. If the reader agrees, then the question is
%2how do you know?%*# Or more precisely, %2what%* is it that you know that
suggests that the complete re-analysis is unwarranted?# What kind of (or
how many) failures would it take before you began to change your mind?#
This is just the sort of knowledge that can be formalized to provide
direction for the problem-solving process. It may possibly be embedded in
one of the conventional approaches, or perhaps in a line-of-reasoning style
second-order strategy: "Don't reconsider the methodology until the next
three KSs have been invoked using the current scheme."
There is one additional approach to all of this that may prove
useful. In an analogy to human behavior, we might organize the system to
allow it to fail "upwards" through different levels of generality in its
attempts to solve the problem.∪∪A similar concept of successive levels of
failure is found in [[Winograd75]. The basic idea is also inherent in
the view of AI as the "science of weak methods" [[Newell69].∪#
Consider the problem of turning on a lamp and noticing that the light does
not come on. We might try a sequence of solutions that looked like:
.BEGINLIST;
(a)\see if the lamp is plugged in,
(b)\try replacing the bulb,
(c)\see if the lamp switch is o.k.,
(d)\see if there is a fuse blown, or
(e)\find out if there has been a power failure.
.ENDLIST;
.skip
.continue
Each failure causes successively fewer assumptions about the state of the
world to be taken for granted and causes a more general approach to the
solution. Analogously, a program failing in its heuristic search via hill
climbing might first re-evaluate its distance metric, then the use of
hill climbing, and finally the use of heuristic search. In this case the
general re-evaluation mechanism is invoked only where necessary.
We can comment, too, on the investment needed for implementation of
this methodology. Since the benefits (and costs) are all incremental, we
need not implement the entire formalism to get any payoff. Even the
smallest steps toward it are useful.
But is all this really necessary? That is, is all of this always
relevant?# Clearly not. There surely are times when systems are written to
achieve a very well-specified purpose and will not necessarily profit from
considering the task in its full generality, as suggested here. It must
therefore be desirable to have such generality as a part of the system
being constructed.
There are, however, two points to be considered. First, even a
system that is not designed for extensive generality may be structured
somewhat more cleanly if the knowledge is viewed along the lines we have
suggested (e.g., in Green's system). Second, it is rare that
all the necessary capabilities of a system can be foreseen in advance, and
redesign is a well-known occupational hazard. Note that the design
and construction of any program (even for a well-understood task domain) is
itself an ill structured problem. Thus, it may still prove useful to
attempt to be general, even in the context of a well-defined task area.
.SS(Summary);
This chapter has proposed a general framework for understanding
strategies as a form of meta-level knowledge and has suggested that any
decision concerning the use of knowledge in problem solving should be
viewed as a strategic choice. It explored how this framework can help make
clear the body of knowledge contained in a program and showed how it can
contribute to both representation design and organization.
Meta-rules were described in detail as one instance of the general
ideas outlined in the framework. We have seen how they help to guide
problem-solving performance and have explored the range of knowledge that they
can be used to represent. Explanation of meta-rules was shown to be
possible with a straightforward extension of the facilities for
object-level rules; steps toward interactive acquisition of meta-rules were
also considered.
We saw that meta-rules refer to object-level rules by describing
(rather than naming) them and that they effect this reference by examining their
content directly. This led to a consideration of the different approaches
to invoking a knowledge source and offered a perspective on the relevant
factors involved. Content-directed invocation was shown to offer a handle
on KSs that provides reliability, expressiveness, and an explicit specification of
invocation criteria. While it requires a significant initial investment of effort,
it can provide a useful level of flexibility for systems with
large knowledge bases subject to frequent changes.
Finally, a taxonomy of strategy types was reviewed, offering a
basis for comparing meta-rules to other forms of strategy encoding. An
examination of the impact of the different forms of encoding led to some
observations about organizing knowledge in ways that help make systems both
easier to construct and more flexible in the face of changes.
ββ